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

littleming · 2016-07-17 12:31:02 · 题解

这道题竟然只有3个人ac了，其实很水，就是题目比较难懂。

而且没有题解。。好吧，我来占楼

废话不多说，看代码

#include<bits/stdc++.h>
using namespace std;
int n,b,w[105],v[30],f[100005],ans;//最大的叫声总和为100000，f和vis数组要开大，当初被卡了好久 
bool vis[100005];
int main()
{
    cin>>n>>b;
    for(int i=1;i<=b;i++)    cin>>v[i];
    vis[0]=1;
    for(int i=1;i<=b;i++)
        for(int j=0;j<=100001-v[i];j++)
            if(vis[j]==1)
            {
                if(vis[j+v[i]]==0)    {f[j+v[i]]=f[j]+1;vis[j+v[i]]=1;}
                else    f[j+v[i]]=min(f[j+v[i]],f[j]+1);
            }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        if(w[i]==0||w[i]==w[i-1]-1)    continue;
        else if(w[i-1]==0)
        {
            if(!vis[w[i]])    {cout<<-1<<endl;return 0;}
            else    ans+=f[w[i]];
        }
        else
        {
            if(!vis[w[i]-w[i-1]+1])    {cout<<-1<<endl;return 0;}
            else    ans+=f[w[i]-w[i-1]+1];
        }
    }
    cout<<ans<<endl;
    return 0;    
}
一道很水的完全背包