题解 P2214 【[USACO14MAR]Mooo Moo S】

· · 题解

一道挺裸的完全背包题，我们可以预处理出每个音量代表的最少的牛的数量。

令 dp[i] 为音量为 i 时最少的牛的数量，则有 dp[i]=\min(dp[i],dp[i-v[j]]+1)，其中，i 为从 1 循环到 10^5 的音量（题目中有说），j 为从 1 寻换到 B 的牛种类的数量。

预处理之后，我们算出每次增加的音量，再查表即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],v[25],dp[105000],ans,x;
int main(){
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)scanf("%d",&v[i]);
    for(int i=1;i<=m;++i)//预处理dp
        for(int j=v[i];j<=100000;++j)dp[j]=min(dp[j],dp[j-v[i]]+1);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);x=a[i];
        if(a[i-1]!=0)x=a[i]-a[i-1]+1;//一个小细节，如果前面一个音量为0，就不会飘过来了。
        ans+=dp[x];//查表
    }
    printf("%d\n",ans);
    return 0;
}
/*
5 2
5 7
0 17 16 20 19

*/