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 |
上AC代码,这题是练习数位DP的好题,重点是区分求0和求其他的数的区别,求 0时要去掉前导0#include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef long long ll; ll dp0[60][60][3],dp[60][60][60]; int a[60]; ll dfs0(int len, int state, int fir, int fp) { if (!len)return state; if (!fp && dp0[len][state][fir] != -1)return dp0[len][state][fir]; ll ret = 0, fpmax = fp ? a[len] : 9; for (int i = 0; i <= fpmax; i++) ret += dfs0(len - 1, state + ((i == 0) && fir), fir || i, fp && i == fpmax); if (!fp)dp0[len][state][fir] = ret; return ret; } ll dfs(int len,int pos, int state,int fp) { if (!len)return state; if (!fp && dp[len][pos][state]!= -1)return dp[len][pos][state]; ll ret = 0, fpmax = fp ? a[len] : 9; for (int i = 0; i <= fpmax; i++) ret += dfs(len - 1,pos,state+(i==pos),fp &&( i == fpmax)); if (!fp)dp[len][pos][state] = ret; return ret; } ll cal(ll n,int x) { if (n == 0)return 0; int len = 0; while (n) { a[++len] = n % 10; n /= 10; } ll ans = 0; if (x==0)return dfs0(len, 0, 0, 1); else return dfs(len, x, 0, 1); } int main() { ll m, n; memset(dp, -1, sizeof(dp)); memset(dp0, -1, sizeof(dp0)); while (scanf("%I64d%I64d",&m,&n)&&m+n) { if (m > n)swap(m, n); for (int i = 0; i < 10;i++) if (i==9)printf("%I64d\n",cal(n,i) - cal(m - 1,i)); else printf("%I64d ", cal(n, i) - cal(m - 1, i)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator