P2214

· · 题解

题目传送门

状态转移方程:dp_i = min(dp_i, dp_{i - V_j})1 \le j \le B

代码: ------------ ```cpp #include <bits/stdc++.h> using namespace std; #define int long long const int M = 20 + 5, N = 100 + 5, K = 1e5 + 5; int n, B; int a[M], b[N], c[N]; int dp[K]; signed main() { scanf("%lld %lld", &n, &B);//输入 for (int i = 1; i <= B; i++) scanf("%lld", &a[i]);//输入 for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);//输入 for (int i = 1; i <= n; i++) { b[i] = c[i] - c[i - 1]; if (c[i - 1] != 0) b[i]++; }//求出每一个牧场单独的声音 for (int i = 1; i <= 1e5; i++) { dp[i] = 1e8;//记住,一定要赋值成一个极大值!!! for (int j = 1; j <= B; j++) { if (i >= a[j]) dp[i] = min(dp[i], dp[i - a[j]] + 1);//状态转移方程 } } int sum = 0; for (int i = 1; i <= n; i++) { if (dp[b[i]] == 1e8) { cout << -1; return 0; }//输出-1 sum += dp[b[i]];//加入总和 } cout << sum;//输出 return 0; } ```