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

贴一份数位dp代码

Posted by youqiong at 2015-08-19 20:19:32 on Problem 3286 and last updated at 2015-08-19 20:22:05
#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:
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