Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一份数位dp代码#include <stdio.h> #include <string.h> __int64 dp[15], L, R; int digit[15]; __int64 dfs(int len, bool isfirst, bool ismax){ if(len == 0) return 0; if(!isfirst && !ismax && dp[len] != -1) return dp[len]; __int64 ret = 0; int mmax = ismax ? digit[len] : 9; for(int i = 0; i <= mmax; ++i){ if(i == 0){ __int64 t = 0; if(!isfirst && i == mmax){ for(int j = len - 1; j >= 1; --j) t = t * 10 + digit[j]; } else if(!isfirst && i != mmax){ for(int j = len - 1; j >= 1; --j) t = t * 10 + 9; } ret += t + 1; } ret += dfs(len - 1, isfirst && i == 0, ismax && i == mmax); } if(!isfirst && !ismax) dp[len] = ret; return ret; } __int64 work(__int64 x){ int len = 0; while(x){ digit[++ len] = (int)(x % 10); x /= 10; } return dfs(len, true, true) - len + 1; } int main (){ memset(dp, -1, sizeof(dp)); while(scanf("%I64d%I64d", &L, &R) != EOF && L >= 0 && R >= 0) printf("%I64d\n", work(R) - work(L - 1)); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator