https://www.luogu.com.cn/problem/P1021
爆搜搜邮票面值,完全背包验证
设dp[j]为面值为j时所用最少邮票数,小于总邮票数则合法
#include<bits/stdc++.h>
using namespace std;
int n,k,dp[10010],answer=0,ans[52],f[52],inf=0x3f3f3f3f;
void dfs(int x)
{
if(x==k+1)
{
register int maxn=0;
while(dp[maxn]<=n)
{
maxn++;
dp[maxn]=inf;
for(register int j=1;j<=k&&maxn-f[j]>=0;j++) dp[maxn]=min(dp[maxn],dp[maxn-f[j]]+1);
}
if(maxn-1>answer)
{
answer=maxn-1;
for(register int i=1;i<=k;i++) ans[i]=f[i];
}
return;
}
int lim=f[x-1]*n+1;
for(register int i=f[x-1]+1;i<=lim;i++)
{
f[x]=i;
dfs(x+1);
}
}
int main()
{
scanf("%d%d",&n,&k);
f[1]=1;
dfs(2);
for(register int i=1;i<=k;i++)
cout<<ans[i]<<" ";
cout<<"\n"<<"MAX="<<answer;//注意输出格式
return 0;
}