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

winmt · 2016-11-12 22:36:14 · 题解

难得的DP大水题，没想到只有这么点人AC。类似于完全背包。

dp[i]代表音量为i时最小的牛的数量，即可列出DP状态转移方程：dp[i]=min(dp[i],dp[i-当前枚举到的牛的音量大小]+1);

然后算出每个田地的实际音量，累加即可。但是不要忘了打“-1”啊！

详见代码：【CPP】（本蒟蒻自认为比楼下写的清晰，明了，好理解2333）

const int INF=2147483647;
int n,k,mx=-1,ans=0;
int v[25],a[105],b[105],dp[100005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i]-max(a[i-1]-1,0);//每个田地的实际音量
        mx=max(mx,b[i]);//记录最大音量，一点点优化。
    }
        //dp
    for(int i=1;i<=mx;i++)dp[i]=INF;//初始化
    for(int i=1;i<=k;i++)
    {
        for(int j=v[i];j<=mx;j++)
        {
            if(dp[j-v[i]]!=INF)dp[j]=min(dp[j],dp[j-v[i]]+1);//一定要判断dp[j-v[i]]!=INF，不然会炸掉！
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dp[b[i]]==INF)
        {
            printf("-1\n");//别忘啦！
            return 0;
        }
        ans+=dp[b[i]];//累加求解
    }
    printf("%d\n",ans);
    return 0;
}
//此题难度是：提高+/省选-？！确定?！明明是普及+/提高-差不多