首页 > 其他 > 详细

CODEVS 1047 邮票面值设计

时间:2017-12-04 21:12:13      阅读:219      评论:0      收藏:0      [点我收藏+]

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;
}

 

CODEVS 1047 邮票面值设计

原文:http://www.cnblogs.com/lhlacm/p/7978943.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!