ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1021　[NOIP 1999 提高组] 邮票面值设计（疑似错题）

来源：洛谷 ★ 1500

DP搜索背包待复习
本题活力0.17按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

[NOIP 1999 提高组] 邮票面值设计（疑似错题）

背景

除直接打表外，本题不保证存在正确且时间复杂度可以通过全部数据做法。由于测试数据过水，部分错误做法可以通过此题，通过不代表做法正确。本题不接受 hack 数据。

关于此类题目的详细内容。

题目描述

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

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

输入格式

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

输出格式

输出共 $2$ 行。

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

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

样例 1

输入：

3 2

输出：

1 3
MAX=7

代码

#include<iostream>
#include <vector> 
using namespace std;
vector<int> a(1000);int n,k,ans;vector<int> f(1000);
void dfs(int x)
{
	if(x==k)
	{
		int dp[3000]={0};
		int i=0;
		while(dp[i]<=n)
		{   i++;
			dp[i]=INT_MAX;
			for(int j=0;j<k&&i-f[j]>=0;j++)
			dp[i]=min(dp[i],dp[i-f[j]]+1);
			
		}
		if(i-1>ans)
		{
			for(int j=0;j<k;j++)
			{
				a[j]=f[j];
			}
			ans=i-1;
		}
		return ;
	}
	for(int i=f[x-1]+1;i<=f[x-1]*n+1;i++)
        {
            f[x]=i;
            dfs(x+1);
        }
}
int main()
{
	
	cin>>n>>k;
	f[0]=1;
	dfs(1);
	for(int i=0;i<k;i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl<<"MAX="<<ans;
}