首页 > 代码库 > 邮票面值设计NOIP1999T
邮票面值设计NOIP1999T
邮票面值设计NOIP1999T
问题描述
给定一个信封，最多只允许粘贴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
3 2
OUTPUT
1 3
MAX=7
思路：深搜加上dp。每次深搜中j的取值范围从上一次+1到上一次能取到的最大值+1，能减少循环次数。对于最大值的取得情况用dp，类似于背包。
#include<iostream>#include<cstring>using namespace std;int n,k,a[41]={0},ansd[41]={0},ans=0,piece[30001]={0};int rmb(int i){ int j,t,maxx; memset(piece,0,sizeof(piece)); for (j=1;j<=i;++j) piece[a[j]]=1; maxx=1; do{ ++maxx; for (j=1;j<=i;++j) if (maxx-a[j]>=0) {if (piece[maxx]==0) piece[maxx]=piece[maxx-a[j]]+1;if (piece[maxx]>piece[maxx-a[j]]+1) piece[maxx]=piece[maxx-a[j]]+1;} if ((piece[maxx]==0)||(piece[maxx]>n)) return maxx-1; } while (true);}void dfs(int i,int maxn){int j;if (i==k+1){if (maxn>ans){ans=maxn;for (j=2;j<=k;++j) ansd[j]=a[j];}return;} for (j=a[i-1]+1;j<=maxn+1;++j){a[i]=j;maxn=rmb(i);dfs(i+1,maxn);}}int main(){int i;cin>>n>>k;a[1]=1;ansd[1]=1;dfs(2,n);for (i=1;i<=k;++i) cout<<ansd[i]<<" ";cout<<endl<<"MAX="<<ans<<endl;}
邮票面值设计NOIP1999T
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。