自动搬运

查看原文

来自洛谷，原作者为

	Nuyoah_awa 事实证明，你没让我失望。

搬运于2025-08-24 21:35:13，当前版本为作者最后更新于2023-04-15 20:14:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有 $B$ 种牛，每种牛的叫声为 $V_i$，每个农场听到的声音为 $x$，求 FarmerJohn 的农场里最少有几头奶牛。

题目分析

看到 $B$ 种奶牛，$n$ 个农场，就想到很像完全背包。所以这道题可以用 DP 做。

我们定义 $dp[i]$ 为 农场中有 $i$ 的声音，最少的奶牛数。

对于每种叫声为 $v[j]$ 的奶牛，声音为 $i$ 的农场的转移方程为：

知道声音为 $i$ 的农场中最少的奶牛数后，我们就可以贪心求解了。

code

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5, INF = 1e9;
int f[N + 5], v[N + 5], n, b, u, now, ans;
int main()
{
	scanf("%d %d", &n, &b);
	for(int i = 0;i <= N;i++)
		f[i] = INF;
	f[0] = 0;
	for(int i = 1;i <= b;i++)
	{
		scanf("%d", &v[i]);
		for(int j = v[i];j <= N;j++)
			f[j] = min(f[j], f[j - v[i]] + 1);
	}
	for(int i = 1, x;i <= n;i++)
	{
		scanf("%d", &x);
		x -= now, now += x;
		now -= now ? 1 : 0;
		if(x < 0)
		{
			printf("-1");
			return 0;
		}
		if(f[x] == INF)
		{
			printf("-1");
			return 0;
		}
		ans += f[x];
	}
	printf("%d", ans);
	return 0;
}