英文题目，比较难懂。大概意思：就是求1到10^9里的数满足每位相加之和等于s的数的个数。
比如1到10^9中的数满足每位相加起来都是1的有10个：1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000；
AC代码如下：
看别人的，还不是太懂，先记下来，慢慢琢磨吧。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 |
#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>using
namespace std;int dp[10][82];int main(){ int
n; memset(dp,0,sizeof(dp)); for(int
i=1;i<10;i++) { dp[1][i]=1;//1位数中每位相加为1……10的都是1个。 } for(int
i=1;i<10;i++)//数的位数，从位数为1到位数为9 { for(int
j=1;j<=i*9;j++)//某个数的各个位数相加之和为j,最大为9*9=81 { for(int
k=0;k<=9&&k<=j;k++)//? { dp[i][j]+=dp[i-1][j-k];//? } } } while(scanf("%d",&n)!=EOF) { int
ans=0; if(n==1)//如和就是1,则就输出10就ok { printf("%d\n",10); continue; } else { for(int
i=1;i<10;i++)//不然将和为n的1到9位数的个数全都加起来 { ans+=dp[i][n]; } printf("%d\n",ans); } } return
0;} |
动态规划（6）——VF（NYOJ269）*,布布扣,bubuko.com
原文：http://www.cnblogs.com/xueniwawa/p/3740093.html