入门...还在学习中，先贴一发
题目链接：
题目大意：
给一个数字n,范围在1~2^63-1，求1~n之间含有49的数字有多少个。
思路：
经典的数位DP，学习了一下，看的别人的代码：
状态转移：
dp[i][0]代表长度为 i 并且不含有49的数字的个数；
dp[i][1]代表长度为 i 并且不含有49，但是最高位是9的数字的个数；
dp[i][2]代表长度为 i 并且含有49的数字的个数。
数组 a[i] 从低位到高位存储 n 的每一位数字。
则：dp[i][0] = dp[i-1][0] * a[i] - dp[i-1][1]; 表示长度为 i 的不含有49的数字的个数等于长度为 i - 1 的不含有49的数字的个数*当前的数字，因为这个位置可以填0~a[i] - 1，然后再减去长度为 i - 1 的最高位是9的数字的个数，因为如果长度为 i - 1 的最高位是9的话，那么高一位就不能填4了，否则就组成了49。
dp[i][1] = dp[i-1][0]; 表示长度为 i 的并且不含有49同时最高位是9的数字的个数等于，长度为 i - 1 的不含有49的数字的个数，因为只要在它的高一位加上一个9就可以了。
dp[i][2] = dp[i-1][2] * a[i] + dp[i-1][1]; 表示长度为 i 的含有49的数字的个数等于，长度为 i - 1 的数字的个数*当前的数字，再加上长度为 i - 1 的并且不含有49同时最高位是9的数字的个数，因为这个时候，只要在高一位加上一个4就可以了，这样在最高的两位就组成了一个49。
做法是从数字的高位向低位扫描，对于第 i 位，
- 首先加上长度为 i - 1 的符合条件的数字个数；
- 再讨论以前是不是出现过49，如果出现过，就要再追加上长度为 i - 1 的不符合条件的数字的个数，因为以前已经有49了；
- 如果没有出现过，就要判断这一位是不是大于4呢，如果大于4，就要再追加上长度为 i - 1 的不含有49但是最高位是9的数字的个数，因为这个时候可以再这一位填4，因为它大于4嘛~；
- 然后就是判断一下，当前位和上一位是不是满足49，如果满足，标记出现了49了！为以后的判断做准备。
其实这个题目还有一个地方不懂，就是为什么要在输入 n 后，要把 n 加1。想了一下特例，比如输入49，按照上面的做法，在第3步，并不会把符合条件的数字加上，因为4不是严格大于4，最后的执行结果就是0，但是如果加上1之后，n就变成了50，这样第3步恰好可以执行，结果就是正确的了。但是对于一般的情况，还是不知道为什么要把n加1……o(╯□╰)o
这题还是卡了很久，照着别人的代码敲的，死活过不了，然后又找了一份代码： 才发现输入输出要用%I64d，这不是坑么……原来hdu要用%I64d，囧……
所以，有时候的bug不是算法或者代码有错误，看看你的输入输出吧！还有，类似的情况，比如，输入文件写错了……更悲剧了。。
#include#include #include #include #include using namespace std;typedef long long LL;LL dp[25][3];LL a[25];unsigned long long n;void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int 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]; }}int main(){ init(); int T; scanf("%d",&T); while(T--) { scanf("%I64d",&n); n++; int len=0; memset(a,0,sizeof(a)); while(n) { a[++len]=n%10; n/=10; } LL ans=0; int last=0; bool flag=false; for(int i=len;i>=1;--i) { ans+=dp[i-1][2]*a[i];//首先加上长度为 i - 1 的符合条件的数字个数； if(flag) //以前是不是出现过49，如果出现过，就要再追加上长度为 i - 1 的不符合条件的数字的个数，因为以前已经有49了； ans+=dp[i-1][0]*a[i]; if(!flag&&a[i]>4) //如果没有出现过，就要判断这一位是不是大于4呢，如果大于4，就要再追加上长度为 i - 1 的不含有49但是最高位是9的数字的个数，因为这个时候可以再这一位填4，因为它大于4嘛~； ans+=dp[i-1][1]; if(last==4&&a[i]==9) //然后就是判断一下，当前位和上一位是不是满足49，如果满足，标记出现了49了！为以后的判断做准备。 flag=true; last=a[i]; } printf("%I64d\n",ans); } return 0;}