题目链接
洛谷 P2214 [USACO14MAR] Mooo Moo S
思路分析
首先，我们要先求出每个牧场产生的音量，由题意第 \(i\) 个牧场音量只需用输入的 \(a_i\) 减去 \(a_{i-1}-1\) 即可。但是，因为每只牛发出的音量都为正，所以如果算出来某个牧场产生的音量为负数，直接输出 -1 即可。
其次，对于求出最少有多少只牛，我们定义 \(dp_j\) 表示音量为 \(j\) 时最少需要的牛的只数，就变成了一个完全背包，以音量为背包容量，牛发出的音量为物品，状态转移方程即为 \(dp_j=\min{(dp_j,dp_{j-v_i}+1)}\)，其中 \(i\) 遍历牛的种类。
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=105,B=25,M=1e5+10;
int n,b;
int v[B],a[N],dp[M];int main(){scanf("%d%d",&n,&b);for (int i=1;i<=b;++i) scanf("%d",v+i);for (int i=1;i<=n;++i) scanf("%d",a+i);for (int i=n;i>1;--i){if (a[i-1]-1>a[i]){ printf("-1");return 0; } // 牧场产生音量为负a[i]-=max(0,a[i-1]-1);}memset(dp,0x3f,sizeof dp);dp[0]=0;for (int i=1;i<=b;++i){for (int j=v[i];j<M;++j) dp[j]=min(dp[j],dp[j-v[i]]+1);}int ans=0;for (int i=1;i<=n;++i){if (dp[a[i]]==0x3f3f3f3f){ printf("-1");return 0; }ans+=dp[a[i]];}printf("%d",ans);return 0;
}