首页 > > 程序设计 > C/C++ >

P1021 邮票面值设计

2018-06-17 22:23:58来源：未知阅读 ()

题目描述

给定一个信封，最多只允许粘贴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 3
MAX=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         else
74         {
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 }