题目

一道很经典的搜索题，可以锻炼搜索的能力，比如可以用dfs覆盖加dp的方式来寻找+更新答案。而且还可以通过在递归中增加数组的方式来辅助搜索。

#include <bits/stdc++.h>

using namespace std;

int n, k, ans[101000], maxn, tot, a[101000];

int ne(int pos, int maxnow)

{

	int dp[10100];

	memset(dp, 4, sizeof(dp));//dp设为最大值。

	dp[0] = 0;

	for (int i = 1; i <= pos; i++)

		for (int j = a[i]; j <= a[pos] * n; j++)//dp判断需要几个数

			dp[j] = min(dp[j - a[i]] + 1, dp[j]);

	for (int i = 1; i <= n * a[pos]; i++)

		if (dp[i] > n)//如果i不行了，说明i-1可以

			return i - 1;

	return a[pos] * n;//返回最大值

}

void dfs(int pos, int maxnow)//覆盖数组

{

	if (pos == k + 1)

	{

		if (maxnow > maxn)

		{

			maxn = maxnow;

			for (int i = 1; i <= k; i++)//更新答案

				ans[i] = a[i];

		}

		return;

	}

	for (int i = ans[pos - 1] + 1; i <= maxnow + 1; i++)

	{

		a[pos] = i;//每一个位置都加以判断。

		int maxx = ne(pos, maxnow);

		dfs(pos + 1, maxx);

	}

}

int main()

{

	scanf("%d%d", &n, &k);

	dfs(1, 0);

	for (int i = 1; i <= k; i++)

		printf("%d ", ans[i]); puts("");

	printf("MAX=%d", maxn);

}