邮票面值设计

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<<"
"<<"MAX="<<answer;//注意输出格式
	return 0;
	
}