Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

上AC代码,这题是练习数位DP的好题,重点是区分求0和求其他的数的区别,求 0时要去掉前导0

Posted by anqing at 2015-07-25 15:13:20 on Problem 2282
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator