题目链接https://www.luogu.com.cn/problem/P1021

又是被oi支配的一天

两种解法，一种是双重暴力，一种是dfs+dp

啊啊啊，太难了。一个都理解不了，有时间再看

暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define N 907
using namespace std;
int n,k,res[N],per[N];// per第i张邮票的面值  res 最后确定的面值 
int last[N],ans;//last记录1-i张邮票最大拼凑的答案 
bool p=false;

void maker(int cnt,int i,int us,int nk){
	if(p)return;
	if(cnt==0){
		p=true;
		return;
	}
	if(us<0 || cnt<0)return;
	if(i==nk+1)
		return;
	for(int a=1;a<=us;a++)
		maker(cnt-a*per[i],i+1,us-a,nk);
	maker(cnt,i+1,us,nk);
}//凑出指定数的搜索 
void update(int u){
	for(int a=last[u-1]+1;;a++){//从上次的最大答案开始往后凑，看看能凑出新的最大为多少 
		p=false;
		maker(a,1,n,u);
		if(!p){
			last[u]=a-1;//找到第一个无法凑出的值，然后更新至这个数-1 
			break;
		}
	}
	return;
}

void dfs(int ik,int las){   //ik 为确定了多少张面值 las 为上一张确定的面值 
	if(ik==k+1){//已经确定好了k张牌 
		if(last[k]>ans){//如果确定的最大的牌比上一次的大 
			ans=last[k];
			for(int a=1;a<=k;a++)
				res[a]=per[a];//更新确定的面值 
		}
		return;
	}
	for(int a=las+1;a<=last[ik-1]+1;a++){//枚举范围  1   ---上一次最大答案往上+1  
		per[ik]=a;//将a纳入第ik张面值 
		update(ik);//更新ik 
		dfs(ik+1,a);
		per[ik]=0;
		last[ik]=0;
	}
}
int main(){
	cin>>n>>k;
	last[1]=n;
	per[1]=1;
	dfs(2,1);
	for(int a=1;a<=k;a++)
		cout<<res[a]<<" ";
	cout<<endl;
	cout<<"MAX="<<ans;
	return 0;
}

dfs+dp

#include<iostream>
#include<cstring>//头文件
using namespace std;
int a[17],n,k,ans[17],maxn;//a【】表示这种方法的邮票，ans【】表示如今取得的解即要输出的
int dp(int t,int mx){
    int f[50000];//f[i]为拼i所需的最少数的个数
    f[0]=0;//边界
    for(int i=1;i<=a[t]*n;i++)
      f[i]=50000;//赋初值赋一个尽可能地大就可以了
    for(int i=1;i<=t;i++)            //从第一位找到目前的位数把所有已找的邮票都枚举 
      for(int j=a[i];j<=a[t]*n;j++)   //因为不可能找到比自己小的数，所以从自己开始找 
        f[j]=min(f[j],f[j-a[i]]+1);    //比较上几次已找到的最小需要位数和即将要找的相比较，取较小值 
for(int i=1;i<=a[t]*n;i++)
      if(f[i]>n)//如果所需最小的个数大于n就意味着这种情况不符合，但f【i-1】是符合的不然f【i-1】就会判断所以不符合返回i-1
        return i-1;
    return a[t]*n;//如果到a【t】*n的f【i】都满足意味着能取到的最大连续数就是a【t】*n
}
void dfs(int t,int mx){              // 为什么全部找完：因为多几张邮票肯定比少几张邮票可能的情况多，所以全部找完是最好的  
    if(t==k+1){        //如果所有邮票数已经找完，那么就和 maxn比较谁更大   
        if(mx>maxn){
            maxn=mx;
            for(int i=1;i<=t-1;i++)
              ans[i]=a[i];} //保存所需要的邮票面值  
        return;
        }
    for(int i=a[t-1]+1;i<=mx+1;i++){  //继续找：为了避免重复，下一张邮票要比上一张邮票大，所以上边界是a[t-1]+1，同时它不能比最大连续值+1还大，不然最大连续值的下一个数就永远连不起来了 
      a[t]=i;
      int x=dp(t,mx);   //动归寻找此时的最大连续数 
      dfs(t+1,x);
    }
}
int main(){
    cin>>n>>k;
    dfs(1,0);  //先从第一张开始找，第一张前面没有数，所以所连续的最大数为 0 
    for(int i=1;i<=k;i++)//输出 注意打空格以及大写换行即可
      cout<<ans[i]<<" ";
    cout<<endl;
    cout<<"MAX="<<maxn<<endl;
    return 0;
}