P2214 [USACO14MAR]哞哞哞Mooo Moo

链接：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;
}

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论