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