题目描述 Description
给定一个信封，最多只允许粘贴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 Description
N和K
输出描述 Output Description
每种邮票的面值，连续最大能到的面值数。数据保证答案唯一。
样例输入 Sample Input
3 2
样例输出 Sample Output
1 3
MAX=7
动态规划加深搜，每枚举一种邮票面值为a[i]的邮票，可能有的最大值在a[i]+1到a[i]*k+1之间。思路是枚举所有可能的邮票组合方式，即枚举面值，分别求得每一种组合方式能得到连续最大能到的面值数，并记录当前的组合方式，就能不断更新这个最大面值数。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,maxn;
int a[];
int num[];
int ans[];
void dp()
{
int i=;
num[]=;
while(num[i]<=n)
{
i++;
num[i]=;
for(int j=;j<k&&i>=a[j];j++)
{
if(num[i-a[j]]+<num[i])
num[i]=num[i-a[j]]+;
}
}
if(i->maxn)
{
maxn=i-;
for(int j=;j<k;j++)
ans[j]=a[j];
}
}
void dfs(int step)
{
if(step==k)
{
dp();
return;
}
for(int i=a[step-]+;i<=a[step-]*n+;i++)
{
a[step]=i;
dfs(step+);
}
}
int main()
{
scanf("%d%d",&n,&k);
maxn=;
dfs();
for(int i=;i<k;i++) printf("%d ",ans[i]);
printf("\nMAX=%d",maxn);
return ;
}