题目描述
给定一个信封，最多只允许粘贴 张邮票，计算在给定
（
）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值
，使在
至
之间的每一个邮资值都能得到。
例如，，
，如果面值分别为
分、
分，则在
分之间的每一个邮资值都能得到（当然还有
分、
分和
分）；如果面值分别为
分、
分，则在
分之间的每一个邮资值都能得到。可以验证当
，
时，
分就是可以得到的连续的邮资最大值，所以
，面值分别为
分、
分。
输入格式
个整数，代表
，
。
输出格式
输出共 行。
第一行输出若干个数字，表示选择的面值，从小到大排序。
第二行，输出 MAX=S， 表示最大的面值。
样例 #1
样例输入 #1
3 2样例输出 #1
1 3
MAX=7#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 907
using namespace std;
int n,k,res[N],per[N];
int last[N],ans;
bool p=false;
void maker(int cnt,int i,int us,int nk){
if(p)return;
if(cnt==0){
p=true;
return;
}
if(us<0 || cnt<0)return;
if(i==nk+1)
return;
for(int a=1;a<=us;a++)
maker(cnt-a*per[i],i+1,us-a,nk);
maker(cnt,i+1,us,nk);
}
void update(int u){
for(int a=last[u-1]+1;;a++){
p=false;
maker(a,1,n,u);
if(!p){
last[u]=a-1;
break;
}
}
return;
}
void dfs(int ik,int las){
if(ik==k+1){
if(last[k]>ans){
ans=last[k];
for(int a=1;a<=k;a++)
res[a]=per[a];
}
return;
}
for(int a=las+1;a<=last[ik-1]+1;a++){
per[ik]=a;
update(ik);
dfs(ik+1,a);
per[ik]=0;
last[ik]=0;
}
}
int main(){
cin>>n>>k;
last[1]=n;
per[1]=1;
dfs(2,1);
for(int a=1;a<=k;a++)
cout<<res[a]<<" ";
cout<<endl;
cout<<"MAX="<<ans;
return 0;
}