Project Euler 164
题目
Numbers
for which no three consecutive digits have a sum greater than a given
value
How many digit numbers (without any leading zero) exist such
that no three consecutive digits of have a sum greater than ?
解决方案
本题是一个明显的数位动态规划。
令 为目前符合题意的 位数中,个位为 ,十位为 的数的个数,为了保证添加连续三个数的和不超过 ,那么个位后面添加的数必须不超过 。
那么可以得到状态转移方程:
由于只有一位数时,十位为 ,因此只要求 。而且,为了防止以后出现前导 ,。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| # include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=20,M=10; ll f[N+4][M][M]; int main(){ for(int i=1;i<=9;i++) f[1][0][i]=1; for(int i=2;i<=N;i++) for(int a=0;a<=9;a++) for(int b=0;a+b<=9;b++) for(int j=0;a+b+j<=9;j++) f[i][a][b]+=f[i-1][j][a]; ll ans=0; for(int a=0;a<=9;a++) for(int b=0;a+b<=9;b++) ans+=f[N][a][b]; printf("%lld\n",ans); }
|