最近遇到了几个数位dp的问题，来总结一下：
一直是看这位大佬的讲解学的，给个链接 http://blog.csdn.net/wust_zzwh/article/details/52100392
直接看题：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3962
题意很简单，就是数字的对应，累计求和，这里需要注意的问题是，过了FFFFFFF之后，就从头开始，另外这个计算量比较大，若是单纯的直接暴力计算是肯定TLE了，因此采用数位dp来进行计算。
#include<cstdio> #include<iostream> #include<cstring> #include<string> using namespace std; #define LL long long int t; LL l,r,n; int dig[20]; int num[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4}; char a[20]; LL dp[20][10010]; //先写个模板好了~ LL dfs(int pos, LL sum, bool limit) { if(pos<0) return sum; if(!limit && dp[pos][sum] != -1) return dp[pos][sum]; int up = limit ? dig[pos] : 15; LL ans = 0; //开始计数 for(int i = 0; i <= up; i++){ ans += dfs(pos-1, sum+num[i], limit && i == dig[pos]); } if(!limit) dp[pos][sum] = ans; return ans; } LL solve(LL n){ //16进制.. for(int i = 0; i < 8; i++){ dig[i] = n; n /= 16; } return dfs(7,0,1); } int main(){ memset(dp,-1,sizeof dp); scanf("%d", &t); while(t--){ scanf("%lld %llX",&r,&n); r--; l = n; r += l; if(r>= (LL) 0xffffffff){ r %= (LL)0xffffffff+1; //过了FFFFFFF就换回去 printf("%lld\n", solve((LL)0xffffffff) - solve(l-1) + solve(r)); } else{ printf("%lld\n", solve(r) - solve(l-1)); } } return 0; }最近没怎么学，博客也没怎么更新，大过年的到处跑，哎。。。。。