C++ [NOIP1999 提高组] 邮票面值设计 详解
[NOIP1999 提高组] 邮票面值设计
题目背景
除直接打表外，本题不保证存在正确且时间复杂度可以通过全部数据做法。由于测试数据过水，部分错误做法可以通过此题，通过不代表做法正确。本题不接受 hack 数据。
题目描述
给定一个信封，最多只允许粘贴 N N N 张邮票，计算在给定 K K K（ N + K ≤ 15 N+K \le 15 N+K≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 M A X \mathsf{MAX} MAX，使在 1 1 1 至 M A X \mathsf{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 \mathsf{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
这题比较难，在洛谷难度普及+/提高
正如题中所说，这题很简单
这一道题不难想出用搜索做，通过枚举枚举出所有种类的邮票，最后判断一下，并记录最大值
但是，直接暴力搜索肯定会超时的，所以我用了以下几个剪枝优化：
（在这里我用a数组记录搜索的值）
剪枝1:我们可以使a数组保持单调递增，dfs中每次从a[k-1]+1开始搜索，以此来消除重复的搜索
剪枝2:我们通过看题，可以知道1肯定会被选用，不然怎么组成1的，所以我们使a[1]=1，然后从第2项开始搜索（这个剪枝意义不大，不过个人喜欢）
剪枝3:这个剪枝可以说是这一道题的难点，
如何判断每次dfs枚举的上界!!!
（每次从a[k-1]+1到50是肯定会超时的）
假设当前准备填第k个（已经填好了k-1）个
所以在前k-1个中可以凑出1-t中的所有整数（需要用dp求出t）
因此我们可以把上界定为t+1
** t+1，不是t，自己想想为什么？**
如果超过了t+1，那么就无法组成t+1了。
所以dfs搜索的范围是
for(int i=a[k-1]+1;i<=t+1;i++)
对了，刚才不是说要用dp吗，那么怎么dp？
dp[i]表示对于当前的a数组组成i所需要最小的个数
所以dp[i]=min(dp[i],dp[i-a[i]]+1)，初始化+oo，dp[0]=0
完整代码（你们最想要的):
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int a[21];//暂时的储存
int maxx=0,ans[21];//ans和maxx记录最终结果
int dp[51000];//dp数组
int solve(int k){
memset(dp,63,sizeof(dp));dp[0]=0;
for(int i=1;i<=k;i++)//前k个数
for(int j=a[i];j<=a[k]*n;j++)//最多能组成到a[k]*n，表示全部都选最大的数
if(dp[j-a[i]]<n)//只能继承的<n
dp[j]=min(dp[j],dp[j-a[i]]+1);//当然是求最小值，以后才可以用
int x=0;
while(dp[x+1]<=100)x++;//得到最长的连续前缀
return x;
}
void dfs(int k){
if(k==m+1){//如果找到m个
int t=solve(k-1);
if(t>maxx){
maxx=t;
memcpy(ans,a,sizeof(ans));
}
return;
}
int end=solve(k-1);
for(int j=a[k-1]+1;j<=end+1;j++){//往下搜索
a[k]=j;dfs(k+1);a[k]=0;
}
}
int main(){
cin>>n>>m;//把n,k改变为n,m
a[1]=1;//剪枝2
dfs(2);//从第2个开始问
for(int i=1;i<=m;i++)printf("%d ",ans[i]);//输出
printf("\nMAX=%d\n",maxx);
return 0;
}
至此，题解结束
- 但是，提一件事
关于评论区的事
- 我都发了10篇文章了，为什么评论区空空如也???
我还是个新手，希望大家能多多指教
- 可为什么评论区空空如也???