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; }