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

题目传送门：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;
}