| ||||||||||
| 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