http://acm.hdu.edu.cn/showproblem.php?pid=3555
第一次做位数DP，卧槽，看了别人一晚上的代码，又调了一早上才做出来，艹艹艹！
这道题讲的是，给定任意n，计算从1~n中有多少数包含连续的49.
--------------------------------------分割线-----------------------------------------------------------
这些是状态转移方程
dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //代表不含49 (当位数增加一位,不含49的数增加10倍,但是要减去一个以9开头的)
dp[i][1]=dp[i-1][0]; //代表不含49,但以9开头(当位数增加一位,就增长了在原来不以9开头的那些) dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; //代表包含49(当位数增加一位,之前已经包含49的增加10倍,另外要加上现在开头为4和之前开头为9组合成49的数)当然状态转移方程不止这一种,如:
dp[k][0]=dp[k-1][0]*9+dp[k-1][1]*8; //dp[][0]表示不包含49并且以非4结尾的个数
dp[k][1]=dp[k-1][0]+dp[k-1][1]; //dp[][1]表示不包含49并且以4结尾的个数
dp[k][2]=dp[k-1][1]+dp[k-1][2]*10; //dp[][2]表示包含49的个数
--------------------------------------分割线-----------------------------------------------------------
另外,此题N (1 <= N <= 2^63-1),所以要输入的话要用字符型(即字符串输入),或定义成long long
#include"stdio.h"#include"stdlib.h"#include"string.h"long long dp[20][3];int main() { int t,len,i,j,a[20],flag,last; long long n,sum; memset(dp,0,sizeof(dp)); //初始化 dp[0][0]=1; for(i=1;i<21;i++) //算出彼此关系,下面计算时,直接调用 { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } scanf("%d",&t); while(t--) { scanf("%I64d",&n); n++; //处理末尾2位是49的特殊情况 len=0; memset(a,0,sizeof(a)); while(n) { a[++len]=n%10; n=n/10; } flag=0; sum=0; last=0; for(i=len;i>=1;i--) { sum+=dp[i-1][2]*a[i]; if(flag) //如果其高位存在49,则低位不管是什么数都存在 sum+=dp[i-1][0]*a[i]; if(!flag&&a[i]>4) //2位置,且首位大于等于5,至少存在低一位有9的情况的个数 sum+=dp[i-1][1]; if(last==4&&a[i]==9) flag=1; last=a[i]; } printf("%I64d\n",sum); } // system("pause");}