首页 > 代码库 > 51nod 1043 幸运号码(数位dp)
51nod 1043 幸运号码(数位dp)
题目链接：51nod 1043 幸运号码
题解：dp[i][j]表示 i 个数和为 j 的总数（包含0开头情况）
dp[i][j] = dp[i-1][j-k]
i & 1 ：这里用滚动数组节省内存
非0开头的情况 * 0开头的情况：(dp[n&1][i]-dp[(n-1)&1][i]) *dp[n&1][i]，最后将其累加即为结果。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define CLR(a,b) memset((a),(b),sizeof((a))) 5 using namespace std; 6 7 const int inf = 0x3f3f3f3f; 8 const int mod = 1e9 + 7; 9 const int N = 1001;10 int n;11 long long dp[2][9*N];//i个数和为j的数量12 int main(){13 int i, j, k;14 long long sum, ans;15 scanf("%d", &n);16 CLR(dp, 0);17 for(i = 0; i <= 9; ++i)18 dp[1][i] = 1;19 for(i = 2; i <= n; ++i){20 for(j = 0; j <= 9*i; ++j){21 sum = 0;22 for(k = 0; k <= 9; ++k){23 if(j >= k)24 sum = (sum + dp[(i-1)&1][j-k]) % mod;25 }26 dp[i&1][j] = sum;27 }28 29 }30 ans = 0;31 for(i = 1; i <= 9*n; ++i){32 ans = (ans + (dp[n&1][i]-dp[(n-1)&1][i]) *dp[n&1][i]) %mod;33 }34 printf("%d\n", ans);35 return 0;36 }
51nod 1043 幸运号码(数位dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。