回溯搜索,DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n,ans,a[1005],b[1005],x[1005];

 int js(int t)
{
	int i,res;
	for (i=1; i<=1000; i++) b[i]=1000000000;
	for (i=1; i<=t; i++) b[a[i]]=1;
	res=0;
	do
	{
		res++;
		for (i=1; i<=t; i++)
			if (res>a[i] && b[res-a[i]]+1<b[res])
				b[res]=b[res-a[i]]+1;
	}while (b[res]<=m);
	return res;
}

 void find(int i)
{
	int k,z;
	z=js(i-1);	
	if (i>n)
	{
		if (z-1>ans) 
		{
			ans=z-1;
			for (int j=1; j<=n; j++) x[j]=a[j];
		}
		return;	
	}
	for (k=z; k>=a[i-1]+1; k--)
	{
		a[i]=k;
		find(i+1);	
	}
}

 int main()
{
	scanf("%d%d",&m,&n);
	a[1]=1;
	find(2);	
	for (int i=1; i<=n; i++) printf("%d ",x[i]); printf("\n");
	printf("MAX=%d\n",ans);
	return 0;
}