数位DP练习
ural 1057 Amount of Degrees （数位DP）
详见：刘聪的论文，写的很详细......
#include <cstdio>#include <iostream>#include <cmath>#include <cstring>using namespace std;int f[11][11];int n,m;int pos[11];void init() { memset(f,0,sizeof(f)); f[0][0] = 1; for(int i=1; i<7; i++) { for(int j=0; j<=9; j++) { if(j == 4) continue; for(int k=0; k<=9; k++) { if(j == 6 && k == 2) continue; f[i][j] += f[i-1][k]; } } }}int solve(int x) { memset(pos,0,sizeof(pos)); int len = 0; int flag = 1; while(x) { pos[++len] = x % 10; if(pos[len] == 4 || (pos[len] == 6 && pos[len-1] == 2)) flag = 0; x /= 10; } int ans = 0; if(flag) ans ++; for(int i=len; i>=1; i--) { for(int j=0; j<pos[i]; j++) { if(j == 4) continue; if( i < len && pos[i+1] == 6 && j == 2) continue; ans += f[i][j]; } if(pos[i] == 4 || (i < len && pos[i+1] == 6 && pos[i] == 2)) break; } return ans;}int main() { init(); while(scanf("%d%d",&n,&m)) { if(n == 0 && m == 0) break; printf("%d\n",solve(m) - solve(n-1)); } return 0;}