[洛谷P1021][NOIP1999 提高组] 邮票面值设计(DP + DFS)

发布于 2022-04-05  1110 次阅读


题目传送门:P1021 [NOIP1999 提高组] 邮票面值设计 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

显然是个搜索,但是如果直接暴力搜索的话,肯定会TLE,所以需要一个搜索的区间。

假设已经得到了前dep种票的面值,且一共有N张,那么为了保证面值之和的连续性下一张票的面值可能是哪些呢?可能是上一张票面值 + 1 直到 前dep种票所能组成的最大数字 + 1(这个右边界会偏大一点点,但是影响并不大)。

为了得到这个N张dep种票能够组成的连续的最大的数,需要用到dp,也就是一个简单的背包问题。

dp[j]表示到前i种票为止,组成面值为j的所需的最小票的数量。如果一个面值j的所需最小数量 > N的话说明这个面值无法通过这dep种票组成。

状态转移方程:

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5010;
int N, K;//N张,K种 
int ans = 0;
int t[maxn],a[maxn];//t临时,a答案 

int f(int dep,int sum)
{
	int dp[maxn];memset(dp, 1, sizeof dp);
	dp[0] = 0;
	//dp[i]表示用前dep张票凑出i面值需要多少张票 
	for(int i = 1;i <= dep; ++ i)
		for(int j = t[i];j <= N * sum; ++ j)
			dp[j] = min(dp[j], dp[j - t[i]] + 1); 
		
	for(int i = 1;i <= N * sum; ++ i)if(dp[i] > N)return i - 1;
	return N * sum;
}

void dfs(int dep,int s,int sum)//dep表示层数,也表示到达了第几种票 
{
	int r = f(dep, sum);
	if(dep > K)
	{
		if(r > ans)
		{
			for(int i = 1;i <= K; ++ i)a[i] = t[i];
			ans = r;
		}
		return ;
	}
	//l表示上一张票的面值,r表示右边界 
	for(int i = s + 1;i <= r + 10; ++ i)//遍历面值 
	{
		t[dep] = i;//记录第dep张票面值为i 
		dfs(dep + 1, i, sum + i);
	}
}

signed main()
{
	cin >> N >> K;
	dfs(1, 0, 0);
	for(int i = 1;i <= K; ++ i)printf("%lld%c",a[i],i == K ? '\n' : ' ');
	printf("MAX=%lld\n",ans);
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09