首页 > 其他 > 详细

HDU - 4734 F(x) (2013成都网络赛,数位DP)

时间:2014-07-13 00:02:51      阅读:439      评论:0      收藏:0      [点我收藏+]

题意:求0-B的满足<=F[A]的所有可能

思路:数位DP,记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

int A, B;
int dp[20][200000];
int bit[20];

int dfs(int cur, int num, int flag) {
	if (cur == -1)
		return num >= 0;
	if (num < 0)
		return 0;
	if (!flag && dp[cur][num] != -1)
		return dp[cur][num];  
	int ans = 0;
	int end = flag?bit[cur]:9;
	for (int i = 0; i <= end; i++) 
		ans += dfs(cur-1, num-i*(1<<cur), flag&&i==end);
	if (!flag)
		dp[cur][num] = ans;
	return ans;
}

int F(int x) {
	int tmp = 0;
	int len = 0;
	while (x) {
		tmp += (x%10)*(1<<len);
		len++;
		x /= 10;
	}
	return tmp;
}

int cal() {
	int len = 0;
	while (B) {
		bit[len++] = B%10;
		B /= 10;
	}
	return dfs(len-1, F(A), 1);
}

int main() {
	int t;
	int cas = 1;
	scanf("%d", &t);
	memset(dp, -1, sizeof(dp));
	while (t--) {
		scanf("%d%d", &A, &B);
		printf("Case #%d: %d\n", cas++, cal());	
	}
	return 0;
}



HDU - 4734 F(x) (2013成都网络赛,数位DP),布布扣,bubuko.com

HDU - 4734 F(x) (2013成都网络赛,数位DP)

原文:http://blog.csdn.net/u011345136/article/details/37657701

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!