题解 P2214 【[USACO14MAR]哞哞哞Mooo Moo】

· · 题解

思路：先进行一次完全背包，背包容量为100000.f[i]定义为当牛场音量为i时该 该牛场最少有几头牛。做完就是模拟了。比如： 0 17 16 20 19 第一个农场声音为0，没有牧场给他传递，所以牛为f[0],第二个牧场，由于前面牧场为0，所以为f[17]（其中前面牧场如果为0，需要特殊处理，看代码）,第三个牧场为f[16-17+1]=f[0]。依次类推。把每个牛场的牛加起来，就得到所有的牛数了。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<string>
#include<iostream>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<map>
#include<set>
#include<stdlib.h>
#include<queue>
#include<sstream>
#include<complex>
#define MAXN  100005
#define eps 0.000001
#define INF 0x3f3f3f3f
#define mod 19260817
#define MIN (-0x7fffffffffffffff)
typedef  long long  LL;
using namespace std;

int f[MAXN];
int val[25];
int ans[MAXN];
int n,m;

void solve()
{
    for(int i=1;i<MAXN;i++)
        f[i]=INF;
    f[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=val[i];j<=MAXN-5;j++)
        {
            f[j]=min(f[j],f[j-val[i]]+1);
        }
    }
    int sum=0;
    ans[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(ans[i-1]==0)
            sum+=f[ans[i]];
        else
           sum+=f[ans[i]-ans[i-1]+1];
        //printf("here:%d\n",sum);
    }
   printf("%d\n",sum);
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&val[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&ans[i]);
    }
    solve();
    return 0;
}