题意 意思 就是 给你一数字，问从 0 到 N 有多少个数字 出现了49；
解题方法 由于有2^64 所以 不要想打表了，用数位dp 吧！ 具体我用了两种方法；说实话，这题 卡了我很久才想通；我用了两种思路，第二种思路，纯属原创，第一种方法，和戴神在ACdream 的一次解题报告一样；不熟悉的话，数位dp 看来也不简单；
数位 dp 首先 一个758457932 则可以看作是 700000000 + 50000000 + 8000000........这样从高位枚举每一个数字，也就是说
先从 0 ～ 100000000 先考虑，然后再 100000000～200000000 发现其实上一个区间包含 49 的数 和这个这个区间包含 49 的数 是一样的，所以，这就是 记忆化搜索，但还是会有影响，比如说，400000000～500000000 也就是说前面的4 后面有9 的话，那后面的 都得考虑进去，但不要紧，因为总共只有三个状态，也就是 带 4 进入后面那个数字，带 49 进入后面那个数字，和什么都不带就进去了， 所以用dp[i][j] 表示进入第 i 个数字所带的状态为 j 时如果进去过，那就直接用就行了。有一个前提条件就是，比如说，第 i 位到达 末位，则不能保存状态，为什么，因为第 i 位到顶了，那么后面那位 就无法取到 9 那么大了；而是自己当前位的值；其实你数字不断变大 的时候你就发现了，到底能不能取9 ， 所有保存的状态都是后面的数全部能取到的值；时间复杂度 就是 案例数T×数字长度×3；很快
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> using namespace std; long long N,k,arr[32]; long long res[32][3]; long long pow( int b ) { long long ans = 1; for( int i = 1; i <= b; i++ ) ans *= 10; return ans; } long long DFS( int flag,int pos,int end ) { if( pos == -1 ){return (flag == 2);} if( !end && res[pos][flag] != -1 ) return res[pos][flag]; if( !end && flag == 2 ) // 要不要都无所谓； { res[pos][flag] = pow(pos+1); return res[pos][flag]; } long long time = (end?arr[pos]:9); long long ans = 0; for( int i = 0; i <= time; i++ ) { int tab = flag; if( flag == 1 && i == 9 ) tab = 2; // 这三步要搞清楚，如果 flag == 2 就不要去改变状态了； if( flag == 0 && i == 4 ) tab = 1; if( flag == 1 && i != 4 && i != 9 ) tab = 0; ans += DFS( tab,pos-1,end && ( i == time ) ); } if( !end ) res[pos][flag] = ans; // 只有后面的状态都能取到就保存； return ans; } void work( ) { memset( arr,0,sizeof(arr) ); k = 0; while( N ) { arr[k++] = N%10; N = N/10; } memset( res,-1,sizeof( res ) ); printf("%I64d\n",DFS( 0,k-1,1) ); } int main( ) { int T; scanf("%d",&T); while( T-- ) { scanf("%I64d",&N); work( ); } return 0; }
第二种方法； 猜 那种 0MS 过掉的方法就是这个吧！
首先 初始化 dp[i] 第几个数从0～9的所有 含49 的个数；
后面一位 如果和前面一位组合成 49：则 49 后面的所有数字都成立；如果没有组成数字则这位对结果没有影响，直接就是前面保存的值；
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> using namespace std; long long N,dp[30][11]; long long pow( long long b ) { long long ans = 1; for( int i = 1; i <= b; i++ ) ans *= 10; return ans; } void inint( ) { memset( dp,0,sizeof(dp) ); dp[1][4] = 1; for( int i = 2; i <= 20; i++ ) for( int j = 0; j <= 9; j++ ) for( int k = 0; k <= 9; k++ ) { if( j == 4 && k == 9 ) dp[i][j] += pow(i-1); else dp[i][j] += dp[i-1][k]; } } long long arr[20]; void work( ) { long long sum = 0; int k = 0; memset( arr,0,sizeof(arr) ); while( N ) { arr[k++] = N%10; N = N/10; } int last = 0; for( int i = k-1; i >= 0; i-- ) // 一位一位的算出来； 先最高位，如果中间出现了 49；则后面都算；然后break； { for( int j = 0; j < arr[i]; j++ ) sum += dp[i][j]; if( last == 4 && arr[i] == 9 ) { long long t = 1; sum++; for( int j = 0; j < i; j++ ) { sum += ( t*arr[j] ); t*=10; } break; } last = arr[i]; } printf("%I64d\n",sum); } int main( ) { int T; inint( ); scanf("%d",&T); while( T-- ) { scanf("%I64d",&N); work( ); } return 0; }