P1021 邮票面值设计

admin

https://www.luogu.org/problemnew/show/P1021

题目描述
给定一个信封，最多只允许粘贴 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

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,k,f[1000],a[17],ans[17],r;
   
4. void dfs(int x)
   
5. {
   
6.     if(x>k)
   
7.     {
   
8.         int o;
   
9.         for(o=1;f[o-1]<=n;o++)
   
10.         {
    
11.             f[o]=99999;
    
12.             for(int i=1;i<=k && o>=a[i];i++)
    
13.                 f[o]=min(f[o],f[o-a[i]]+1);
    
14.         }
    
15. 
    
16.         o-=2;
    
17.         if(r<o)
    
18.         {
    
19.             r=o;
    
20.             for(int i=1;i<=k;i++)
    
21.                 ans[i]=a[i];
    
22.         }
    
23.         return;
    
24.     }
    
25.     for(int i=a[x-1]+1;i<=a[x-1]*n+1;i++)
    
26.     {
    
27.         a[x]=i;
    
28.         dfs(x+1);
    
29.     }
    
30. }
    
31. int main()
    
32. {
    
33.     cin>>n>>k;
    
34.     a[1]=1;
    
35.     dfs(2);
    
36.     for(int i=1;i<=k;i++)
    
37.         cout<<ans[i]<<" ";
    
38.     cout<<endl;
    
39.     cout<<"MAX="<<r<<endl;
    
40.     return 0;
    
41. }
    

复制代码

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. #include <cmath>
   
5. #include <cstdlib>
   
6. #include <algorithm>
   
7. #include <queue>
   
8. #include <stack>
   
9. using namespace std;
   
10. int n,k,a[10000],ans[10000],maxn=-0x3f3f3f3f;
    
11. int suan(int x)
    
12. {
    
13.         int f[10000];
    
14.         f[0]=0;
    
15.         for(int i=1;i<=a[x]*n;i++)
    
16.                 f[i]=0x3f3f3f3f;
    
17.         for(int i=1;i<=x;i++)
    
18.                 for(int j=a[i];j<=a[x]*n;j++)
    
19.                         f[j]=min(f[j],f[j-a[i]]+1);
    
20.         for(int i=1;i<=a[x]*n;i++)
    
21.                 if(f[i]>n)
    
22.                         return i-1;
    
23.         return a[x]*n;
    
24.                        
    
25. }
    
26. void dfs(int num,int ma)
    
27. {
    
28.         if(num==k)
    
29.         {
    
30.                 if(ma>maxn)
    
31.                 {
    
32.                         maxn=ma;
    
33.                         for(int i=1;i<=k;i++)
    
34.                                 ans[i]=a[i];
    
35.                 }
    
36.                 return;
    
37.         }
    
38.         for(int i=a[num]+1;i<=ma+1;i++)
    
39.         {
    
40.                 a[num+1]=i;
    
41.                 dfs(num+1,suan(num+1));
    
42.         }
    
43. }
    
44. int main()
    
45. {
    
46.         scanf("%d%d",&n,&k);
    
47.         a[1]=1;
    
48.         dfs(1,n);
    
49.         for(int i=1;i<=k;i++)
    
50.                 printf("%d ",ans[i]);
    
51.         printf("\nMAX=%d",maxn);
    
52.         return 0;
    
53. }

复制代码

admin

怎么好像比我的药复杂？看我的程序：

1. //NOIP99邮票问题
   
2. #include<iostream>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int a[10],b[10],s[1000];
   
6. //S[i]表示贴到面值为i至少需要几张邮票
   
7. int n,k,maxs,i,t;
   
8. int getmax(int l)
   
9. {
   
10.     int i,j,p,q,r  ;
    
11.     for (i=2; i<=999; i++)
    
12.     {
    
13.         r=s[i-1]+1;//任何一种面值均可以由前面一个加上一张一分的
    
14.         j=2;  //从第二个邮票面值开始试
    
15.         p=i-a[j];  //假定由i-a[j]+当前的面值贴出
    
16.         while ((p>=0)&&(j<=l))
    
17.         {
    
18.             q=s[p]+1;  //如此贴出
    
19.             if (r>q) r=q;//检测最小
    
20.             j++;p=i-a[j];
    
21.         }
    
22.         s[i]=r;if (s[i]>n)  break;
    
23.     }
    
24.     return i-1;
    
25. }
    
26. void dfs(int i)
    
27. {
    
28.     int  j,temp=getmax(i-1);
    
29.     if (i>k)
    
30.     {
    
31.         if (temp>maxs){maxs=temp;for (int ii=0; ii<=9; ii++) b[ii]=a[ii];}
    
32.     }
    
33.     else
    
34.         for (j=a[i-1]+1; j<=temp+1; j++){a[i]=j;dfs(i+1);}
    
35. }
    
36. int main()
    
37. {
    
38.     cin>>n>>k;
    
39.     a[1]=1;maxs=1;
    
40.     s[0]=0;s[1]=1;
    
41.     dfs(2);
    
42.     for (i=1; i<=k; i++) cout<<b[i]<<' ';
    
43.     cout<<endl<<"MAX="<<maxs;
    
44. }
    
45. 
    

复制代码

admin

怎么好像比我的药复杂？看我的程序：

1. //NOIP99邮票问题
   
2. #include<iostream>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int a[10],b[10],s[1000];
   
6. //S[i]表示贴到面值为i至少需要几张邮票
   
7. int n,k,maxs,i,t;
   
8. int getmax(int l)
   
9. {
   
10.     int i,j,p,q,r  ;
    
11.     for (i=2; i<=999; i++)
    
12.     {
    
13.         r=s[i-1]+1;//任何一种面值均可以由前面一个加上一张一分的
    
14.         j=2;  //从第二个邮票面值开始试
    
15.         p=i-a[j];  //假定由i-a[j]+当前的面值贴出
    
16.         while ((p>=0)&&(j<=l))
    
17.         {
    
18.             q=s[p]+1;  //如此贴出
    
19.             if (r>q) r=q;//检测最小
    
20.             j++;p=i-a[j];
    
21.         }
    
22.         s[i]=r;if (s[i]>n)  break;
    
23.     }
    
24.     return i-1;
    
25. }
    
26. void dfs(int i)
    
27. {
    
28.     int  j,temp=getmax(i-1);
    
29.     if (i>k)
    
30.     {
    
31.         if (temp>maxs){maxs=temp;for (int ii=0; ii<=9; ii++) b[ii]=a[ii];}
    
32.     }
    
33.     else
    
34.         for (j=a[i-1]+1; j<=temp+1; j++){a[i]=j;dfs(i+1);}
    
35. }
    
36. int main()
    
37. {
    
38.     cin>>n>>k;
    
39.     a[1]=1;maxs=1;
    
40.     s[0]=0;s[1]=1;
    
41.     dfs(2);
    
42.     for (i=1; i<=k; i++) cout<<b[i]<<' ';
    
43.     cout<<endl<<"MAX="<<maxs;
    
44. }
    
45. 
    

复制代码