P2214 [USACO14MAR] Mooo Moo S 解题笔记

思路：

完全背包问题。

对每个牧场做类似于差分的操作，求出每个牧场自身需要达到多少的音量。然后再对每个牧场需要达到的音量进行完全背包的操作，将答案统计进变量cnt中，最后输出cnt即可。

中途出现的错误：

1. 完全背包模板中，每头牛的编号写成了每个容量。
2. dp 数组未给出起始条件，应当dp[0] = 0。
3. 未判断不可解的情况，导致Wa了一个点。

code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a[105], b[105], dp[1000005], sum[105], cnt;
signed main() {cin >> n >> m;for(int i = 1;i <= m;i ++)  {cin >> b[i];}for(int i = 1;i <= n;i ++) {cin >> a[i];sum[i] = a[i] - a[i - 1];if(i != 1 && a[i - 1] > 1) sum[i] += 1;else if(i == 1 && a[i - 1] > 1) sum[i] += a[i - 1], sum[i] -= 1;if(sum[i] < 0) {cout << -1;return 0;}}for(int i = 1;i <= n;i ++) {if(sum[i] == 0) continue;for(int i = 0;i < 1000005;i ++) {dp[i] = 1e9;}dp[0] = 0;for(int j = 1;j <= sum[i];j ++) {for(int k = 1;k <= m;k ++) {if(b[k] <= j) dp[j] = min(dp[j], dp[j - b[k]] + 1);}}if(dp[sum[i]] == 1e9) {cout << -1;return 0;}cnt += dp[sum[i]];}cout << cnt;
}