P1021 邮票面值设计
题目意思是你最多用n张邮票，你可以自己设定k种邮票的面值，每种邮票数量无穷，你最多能用这k种邮票在不超过n张的情况下，组合成的价值要求是从1开始连续的，
求最大能连续到多少；
有完全背包背包的身影，我们知道每个物品的重量是1，但是我们不知道每个物品的价值是多少，这需要我们枚举；
我们如何枚举？
对于当前第x种邮票，它能赋予的值得范围是什么？
显然我们不能赋值前面已经使用过的数，我们需要的是让连续的最大数增长；
那就是前一个数+1，但是不能超过前面使用过的数能表示的最大值+1。否则表示的数是不连续的；
因为前面的数连续最大能表示mx,再加一个mx+2或者更大的数是不能表示mx+1的；
加上我们刚赋值的数能表示的最大值是多少？
完全背包解决问题；
设f[j]表示价值为j时最少用几张邮票；
然后从1开始遍历到a[now]*now（能表示的最大值，虽然可能达不到），再判断一下边界n就好了；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
int n,k;
int f[maxn];
int mon[],ans[],ans_mx; int dp(int x,int mx)
{
memset(f,0x3f,sizeof(f));
f[]=;
for(int i=;i<=x;i++)
{
for(int j=mon[i];j<=mon[x]*n;j++)
{
f[j]=min(f[j],f[j-mon[i]]+);
}
}
for(int i=;i<=mon[x]*n;i++)
{
if(f[i]>n) return i-;
}
return mon[x]*n;
} void dfs(int x,int mx)
{
if(x==k+)
{
if(mx>ans_mx)
{
ans_mx=mx;
for(int i=;i<=k;i++) ans[i]=mon[i];
}
return ;
}
for(int i=mon[x-]+;i<=mx+;i++)
{
mon[x]=i;
int now_mx=dp(x,mx);
dfs(x+,now_mx);
}
}
int main()
{
scanf("%d%d",&n,&k);
dfs(,);
for(int i=;i<=k;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
printf("MAX=%d\n",ans_mx);
return ;
}