P2214 [USACO14MAR] Mooo Moo S
题目背景
农夫约翰完全忘了他有多少头牛了！他不好意思到牧场里去数牛，因为他不想让牛意识到他的健忘。取而代之的是，他决定在奶牛聚集的牧场里安装麦克风，秘密计算出他能从中听到的所有牛叫声的总音量，以便以此确定奶牛的数量。
题目描述
FJ 的 \(N(1\le N\le100)\) 个牧场都是沿着一条笔直的道路分布的。每一个牧场可能有许多种品种的奶牛；FJ 拥有 \(B(1\le B\le20)\) 个不同品种的奶牛，而第 \(i\) 种奶牛的叫声音量为 \(V_i(1\le V_i\le100)\)。此外，有一股强风沿着道路吹来，将牛的叫声从左往右传递，如果某个牧场的总音量是 \(x\)，那么它将传递 \(x-1\) 的音量到右边的下一个牧场。这就意味着，一个牧场里的总音量是处在该牧场的奶牛所发出的音量加上左边前一个牧场的总音量 \(-1\)。数据保证，每一个牧场内由该牧场所有奶牛所发出的总音量最多为 \(10^5\)。
输入格式
第 \(1\) 行：两个用空格分隔的整数 \(N\) 和 \(B\)。
第 \(2 \sim B+1\) 行：第 \(i+1\) 行包含整数 \(V_i\) 。
第 \(B+2 \sim B+N+1\) 行：第 \(B+i+1\) 行表示在第 \(i\) 个牧场内所能监听到的总音量。
输出格式
共一行，即 FJ 拥有的最小奶牛数量。
如果 FJ 不可能拥有一种牧场配置满足给出的条件，输出 \(-1\)。
输入输出样例 #1
输入 #1
5 2
5
7
0
17
16
20
19
输出 #1
4说明/提示
输入说明：
FJ 拥有 \(5\) 个牧场，每个牧场总音量从左到右分别为为 \(0\)、\(17\)、\(16\)、\(20\)、\(19\)。FJ 有两种不同品种的奶牛；第一种奶牛的叫声音量是 \(5\)，第二种奶牛的叫声音量是 \(7\)。
输出说明：
\(2\) 号牧场场有 \(2\) 头 \(1\) 号品种的奶牛，\(1\) 头 \(2\) 号品种奶牛；还有一头牛在 \(4\) 号牧场，共 \(4\) 头奶牛。
解题思路：
读题后不难看出 ，第一步算出属于当前牛棚的音量。在算当前音量拥有牛的最小值，最后累加。
简单的完全背包。前音量为背包容量，&V_{i}&为物品体积，价值为1，求最小价值。
//转换为01背包和完全背包求解，速度最快，复杂度O(V*Σlog n[i])
#include <bits/stdc++.h>
using namespace std;
int dp[1000000];
int n, m;
int arr[300], u[500];
int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> arr[i];}for (int i = 1; i <= n; i++) {cin >> u[i];}dp[0] = 0;for (int j = 1; j <= 100000; j++) {dp[j] = 9999999;}for (int j = 1; j <= m; j++) {//求不同容量的最小价值for (int l = arr[j]; l <= 100000; l++) {dp[l] = min(dp[l - arr[j]] + 1, dp[l]);}}// for (int j = 1; j <= 100; j++) {// cout << dp[j] << " ";// }int ans = 0;for (int i = 1; i <= n; i++) {int x = u[i];if (u[i - 1] != 0) {x = u[i] - u[i - 1] + 1;}if (x <= 0 || u[i] == 0) continue;ans += dp[x];}cout << ans << endl;return 0;
}