链接：Miku
----------------------
这道题还是个背包
---------------------
首先看一下声音的组成，对于每一个农场的声音，它是由两部分组成的 ：上一个农场的声音-1（如果有的话）+这个农场的声音（如果有的话）
，并且声音也之和上个农场的总声音有关（注意，总声音，上个）和这个农场，所以我们可以递推出每一个农场的声音。
-----------------------
那么每一个声音代表多少牛呢？这是一个完全背包问题。我们设dp[i]为声音为i的时候的最小牛数量，并且把每种牛的声音看作体积，数量为价值，很明显，就是
价值最小的完全背包，背包最大体积是多少呢？100000（猜猜为什么）
----------------------
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100000; int dp[100000]; int v[101]; int n,b; int ans; int voi[101]; int f; int vo; int main(){ scanf("%d%d",&n,&b); for(int i=1;i<=b;++i){ scanf("%d",&v[i]); } memset(dp,0x7f,sizeof(dp)); dp[0]=0; for(int i=1;i<=b;++i){ for(int j=v[i];j<=maxn;++j){ dp[j]=min(dp[j],dp[j-v[i]]+1); } } for(int j=1;j<=n;++j){ scanf("%d",&v[j]); voi[j]=v[j]; } //for(int i=1;i<=20;++i){ // cout<<dp[i]<<endl; //} for(int i=1;i<=n;++i){ if((v[i]!=0)&&(voi[i-1]!=0)){ v[i]=v[i]-voi[i-1]+1; } if(v[i]!=0) ans+=dp[v[i]]; // cout<<v[i]<<" "; } cout<<ans; return 0; }
原文：https://www.cnblogs.com/For-Miku/p/12274089.html
