贤鱼的刷题日常-P1021 [NOIP1999 提高组] 邮票面值设计-题目详解

🏆今日学习目标： 🍀学习了解P1021 [NOIP1999 提高组] 邮票面值设计 ✅创作者：贤鱼 ⏰预计时间：15分钟 🎉个人主页：贤鱼的个人主页 🔥专栏系列：c++

[NOIP1999 提高组] 邮票面值设计 题目描述

给定一个信封，最多只允许粘贴 N N N 张邮票，计算在给定 K K K（ N + K ≤ 15 N+K \le 15 N+K≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 M A X MAX MAX，使在 1 1 1 至 M A X MAX MAX 之间的每一个邮资值都能得到。

例如， N = 3 N=3 N=3， K = 2 K=2 K=2，如果面值分别为 1 1 1 分、 4 4 4 分，则在 1 ∼ 6 1\sim 6 1∼6 分之间的每一个邮资值都能得到（当然还有 8 8 8 分、 9 9 9 分和 12 12 12 分）；如果面值分别为 1 1 1 分、 3 3 3 分，则在 1 ∼ 7 1\sim 7 1∼7 分之间的每一个邮资值都能得到。可以验证当 N = 3 N=3 N=3， K = 2 K=2 K=2 时， 7 7 7 分就是可以得到的连续的邮资最大值，所以 M A X = 7 MAX=7 MAX=7，面值分别为 1 1 1 分、 3 3 3 分。

输入格式

2 2 2 个整数，代表 N N N， K K K。

输出格式

输出共 2 2 2 行。

第一行输出若干个数字，表示选择的面值，从小到大排序。

第二行，输出 MAX=S， S S S 表示最大的面值。

样例 #1 样例输入 #1

3 2

样例输出 #1

1 3
MAX=7

思路

挺狗的题，深搜+动态规划

首先如何搜索很简单，主要是难在动态规划上

这里我们用dp[i]储存组成面值i用的最小的邮票数 a储存每一位的面值 我们直接从a[i-1]+1搜索到当前可以组成的最大值就可以了（如果选个1，2后面选择10，岂不是好多没法组成）

AC代码

#include
#include
#include
#include
using namespace std;
int dp[10001],a[10001];
int n,k;
int maxx=-1;
int ans[10001];
int pd(int m){
	memset(dp,10101,sizeof(dp));
	dp[0]=0;
	for(int i=1;ik;
	a[1]=1;
	dfs(2);//第一个必须是1没毛病吧，所以从第二个开始搞
	for(int i=1;i