1047 邮票面值设计

 

1999年NOIP全国联赛提高组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 

 

 

题目描述 

Description

 

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

   

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

输入描述 

Input Description

N和K

输出描述 

Output Description

每种邮票的面值，连续最大能到的面值数。数据保证答案唯一。

样例输入 

Sample Input

3 2

样例输出 

Sample Output

1 3

MAX=7

思路：

先用dfs+剪枝找出所以符合要求的邮票种类，再用dp（01背包）。

看代码：

#include <iostream> #include <algorithm> using namespace std; int n,k,maxn=0; int num[41],dp[4000001],ans[41]; void dpf(){ int t=0; dp[0]=0; while(dp[t]<=n){ t++; dp[t]=41; for(int j=1;j<=k&&t>=num[j];j++){ dp[t]=min(dp[t],dp[t-num[j]]+1); } } cout<<t<<endl; if(t-1>maxn){ maxn=t-1; int i; for(i=1;i<=k;i++) ans[i]=num[i]; } } void dfs(int l){ if(l-1==k){ dpf(); return; } int i; for(i=num[l-1]+1;i<=num[l-1]*n+1;i++){ num[l]=i; dfs(l+1); } } int main(){ num[1]=1; cin>>n>>k; dfs(2); int i; for(i=1;i<=k;i++){ if(i==k) cout<<ans[i]<<endl; else cout<<ans[i]<<" "; } cout<<"MAX="<<maxn<<endl; }