洛谷P1021 邮票面值设计

https://www.luogu.org/problem/P1021

#include<cstdio>
#include<cstring>
#include<iostream> 
using namespace std;
int res;
int f[10005];
int n;
int tmp[10005];
int check(int now,int sum)//完全背包判断连续
{
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=now;i++)
    {
        for(int j=tmp[i];j<=sum*n;j++)//完全背包
        {
            f[j]=min(f[j],f[j-tmp[i]]+1);
        }
    }
    for(int i=1;i<=n*sum;i++)
    {
        if(f[i]>n)//如果超过n了，那就是前一个
        {
            return i-1;
        }
    }
    return n*sum;
}
int k;
int ans[20];
void dfs(int now,int last,int maxl,int sum)//当前为第now个，上一个是last，之前的最大连续的最后一个值为maxl，和已经是sum了
{
    if(now>k)//如果已经搜完一个了
    {
        if(res<maxl)//判断最大连续的是否大于res
        {
            res=maxl;//更新
            for(int i=1;i<=k;i++)
            {
                ans[i]=tmp[i];//把ans数组更新
            }
        }
        return ;//这一层完了，返回
    }
    for(int i=last+1;i<=maxl+1;i++)
    {
        tmp[now]=i;//记录
        int x=check(now,sum+i);//背包判断max
        dfs(now+1,i,x,sum+i);//下一层
    }
    return ;
}
int main()
{
    scanf("%d%d",&n,&k);
    dfs(1,0,0,0);
    for(int i=1;i<=k;i++)
    {
        printf("%d ",ans[i]);
    }
    printf("\nMAX=%d\n",res);
    return 0;
}