题解 P2214 【[USACO14MAR]Mooo Moo S】
OItby
·
·
题解
- 本想找个$RMQ$练手，却遇到了一道裸裸的**完全背包**
- [博客](https://www.cnblogs.com/hihocoder/p/12355644.html)实用效果更佳
------
## 题解
我们可以通过每一个农场的总音量还原出该农场的牛产生的音量
题目要我们求的是最小奶牛数，很显然，具有最优子结构的性质，**即**我们只有让每一个农场的奶牛数最少,总奶牛数一定就是最小值
已知每一种奶牛的声音和每一个农场的总声音，求每个农场的最小奶牛数，题目中没有限定每种奶牛的数量，相信诸位一定能看出这就是一个**完全背包**
这样就诞生了我的代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=101,M=100001;
int n,b,m,f[M],w[N],v[N];
int main()
{
scanf("%d%d",&n,&b);
for(int i=1;i<=b;++i) scanf("%d",&w[i]);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
for(int i=n;i>1;--i)
if(v[i-1]) v[i]-=v[i-1]-1;//倒序还原每一个农场的牛产生的音量，正序的话会覆盖，注意我的特判
for(int i=1;i<=n;++i) m=max(m,v[i]);
for(int i=1;i<=m;++i) f[i]=1e+7;
for(int i=1;i<=b;++i)
for(int j=w[i];j<=m;++j)
f[j]=min(f[j],f[j-w[i]]+1);//完全背包
int Ans=0;
for(int i=1;i<=n;++i)
if(f[i]<1e+7) Ans+=f[v[i]];
else {puts("-1");return 0;}//无法用奶牛构成这种声音
printf("%d\n",Ans);
return 0;
}
```