CF632E Thief in a Shop 题解

思路

题目要问的，是 $k$ 个物品最多能组成多少种不同的权值之和（每个数量不限）。

正着求当然很麻烦，但是反着解相对来说就简单多了。

所以我们可以将题目转化为：

求凑某个权值和最少要多少物品，如果最少个数比 $k$ 要大，则这个权值和就无法凑出。

题目分析到这里，就不难看出是背包 dp 了。

代码实现

状态转移

我们用 $d{p}_i$ 表示凑出权值和为 i 最少需要多少件物品。

01 背包问题这里不多阐述了。

则可以得到状态转移方程为：$d{p}_i\leftarrow \min d{p}_i,d{p}_{i-a_j}+1$。

（j 为从 1 到 $n$ 个物品中满足 $a_j\le i$ 的物品。）

---

优化

这里做一个简单的优化：

我们让权值最小的物品的权值为 0，其余的物品权值都减去最小的权值。

这样，最后当 $d{p}_i<k$（即数量不足）时，

可以用权值最小（刚刚权值清 0）的那个物品补上。

同时，在 dp 的时候我们也不用顾忌到数量要求了。

---

代码

（更多细节请见代码及注释。）

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int n, k;
int limi;
int a[maxn], dp[maxn * maxn];

int read ()
{
	int x = 1, s = 0;
	char ch = getchar ();
	while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();}
	while (ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar ();
	return x * s;
}

int main ()
{
	memset (dp, 1e4, sizeof dp);//记得初始化 
	n = read (), k = read ();
	for (register int i (1); i <= n; ++i) a[i] = read ();
	
	sort (a + 1, a + n + 1);
	int tmp = a[1];
	for (register int i (1); i <= n; ++i) a[i] -= tmp;//记得是减去 kmp 而不是 a[1] 
	limi = k * a[n];
	dp[0] = 0;
	for (register int i (1); i <= limi; ++i)
	for (register int j (1); j <= n; ++j) if (a[j] <= i) dp[i] = min (dp[i], dp[i - a[j]] + 1);
	
	for (register int i (0); i <= limi; ++i) if (dp[i] <= k) printf ("%d ", i + tmp * k);//都要加上 kmp 因为之前减去了 
	return 0;
}

感谢阅读~