首页 > 代码库 > P1021 邮票面值设计

P1021 邮票面值设计

2024-10-11 07:41:38   208人阅读

题目描述

给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值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分。

输入输出格式

输入格式：

2个整数，代表N，K。

输出格式：

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

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

输入输出样例

输入样例#1：
3 2
输出样例#1：
1 3MAX=7

写了个dp，写了个深搜结果慢的和乌龟一样。。
不过幸亏有数据，
思路：深搜枚举，背包DP求值
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=1001; 7 void read(int & n) 8 { 9     char c=‘+‘;int x=0;int flag=0;10     while(c<‘0‘||c>‘9‘)11     {    if(c==‘-‘)    flag=1;    c=getchar();    }12     while(c>=‘0‘&&c<=‘9‘)13     {    x=x*10+(c-48);    c=getchar();}14     flag==1?n=-x:n=x;15 }16 int n,k;17 bool vis[MAXN];18 int ans[MAXN];// 每一次选的数19 int dp[MAXN];// 记录每一个数是否有方案可以达到 20 int maxnum;21 int out[MAXN];22 int ed=0;23 inline int pd()24 {25     memset(dp,0x3f,sizeof(dp));26     dp[0]=0;27     int ok=0;28     int tot=0;29     for(int i=1;i<=k;i++)30     tot=max(ans[i]*n,tot);31     for(int i=1;i<=k;i++)// 每一种物品 32         for(int j=ans[i];j<=n*ans[i];j++)33             if(dp[j-ans[i]]+1<=n)34             dp[j]=min(dp[j],dp[j-ans[i]]+1);35     for(int i=1;i<=170;i++)36     {37         if(dp[i]<888)38         {39             ok++;40             continue;        41         }    42         else break;43     }44     return ok;45 }46 inline void dfs(int now,int num)// now已经选的数量，num最后一数 47 {48     ans[now]=num;49     if(now==k)50     {51         int hh=pd();52         //cout<<hh<<"****"<<endl;53         if(hh>maxnum)54         {55             for(int i=1;i<=k;i++)56                 out[i]=ans[i];57             //memset(ans,0,sizeof(ans));58             //cout<<maxnum<<"****"<<endl;59             maxnum=max(maxnum,hh);60             ed=max(maxnum,ed);61         }62         return ;63     }64     for(int i=num+1;i<=51&&i<=n*num+5;i++)65     {66         if(vis[i]==0)67         {68             vis[i]=1;69             if(now+1<=k)70             dfs(now+1,i);71             vis[i]=0;72         }73         else74         {75             vis[i]=1;76             dfs(now,num);77             vis[i]=0;78         }79         80     }81 }82 int main()83 {84     read(n);read(k);85     vis[1]=1;86     dfs(1,1);// 选的第一个数是1，已经选了一个 87     for(int i=1;i<=k;i++)88         printf("%d ",out[i]);89         cout<<endl;90     printf("MAX=%d",ed);91     return 0;92 }

 

 

P1021 邮票面值设计


联系
我们