洛谷P2744 量取牛奶

题目

DP或者迭代加深搜索，比较考验递归的搜索。

题目第一问可以用迭代加深搜索限制层数。

第二问需要满足字典序最小，所以我们可以在搜索的时候把比当前答案字典序大的情况剪枝掉。

然后考虑怎么搜索，对于每一位我们都要先搜索出每一位所能到达的所有情况包括选或者选几个。

#include <bits/stdc++.h>

#define N 1000101

using namespace std;

int q, n, d, ok;

int a[N], dp[N], vis[N], temp[N], ans[N];// vis[i]表示a[i]是否被选择

void dfs(int dep, int top, int pos)//该题目要求字典序最小因此我们必须对每个位置所有的情况都找完，才能 找下一位置。

{

 	if (dep == d && top == 0)

 	{

 		ok = 1;

 		memcpy(ans, temp, d << 4);//覆盖答案

 		return;

 	}

 	if (pos > n || a[pos] > ans[dep] || dep > d || top < 0)  return;

 	temp[dep] = a[pos];

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

 		dfs(dep + 1, top - i * a[pos], pos + 1);

 	if (pos < n)//也要枚举当前数不选的情况。

 		dfs(dep, top, pos + 1);//dep不用变，下次搜索会覆盖。

}

int main()

{

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

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

 		scanf("%d", &a[i]);

 	sort(a + 1, a + 1 + n);

 	n = unique(a + 1, a + 1 + n) - a - 1;

 	memset(ans, 123, sizeof(ans));

 	for (d = 1; d <= n; d++)//枚举最多用几个桶

 	{

 		dfs(0, q, 1);

 		if (ok) break;

 	}

 	printf("%d ", d);

 	for (int i = 0; i < d; i++)

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

 	return 0;

}