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

· · 题解

背包问题之方案数

这题就是一个方案数问题，用f[i]表示声音为i的方案数，其中方案数要求最少，那初始化肯定是有的。然后我是利用顺推得思想，如果f[j]存在，那么f[j+w]也存在，且分f[j+w]的方案数=min(f[j]+1,f[j+w])，因为我们不知道它有多少条牛。只告诉你声音最多不超过100000，那我们直接把100000看成容量就行了。

然后对于声音，它每次都会遗留上次的声音，就可以用一个last表示，但是因为上次的声音不是这次发出的所以要减去它，为了避免now的值被改变导致last存储失败，就多开一个变量b，用来保存没用减去上次声音的now。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m,p,ans,last,now,b;
int f[100002],w;//100001是70分，不知道为什么。。。明明数据能过，可就是70。。。
void read(int &f)//输入优化
{
    f=0;char c;bool d=0;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=1;f=f*10+c-48;
    while (c=getchar(),c>='0'&&c<='9') f=f*10+c-48;
    if (d) f*=-1;
}
int main()
{
    read(n);read(m);memset(f,127/3,sizeof(f));//初始化
    f[0]=0;
    r(i,1,m) 
     {read(w);//这样做是可以节省一个数组
     r(j,0,100001)
        f[j+w]=min(f[j]+1,f[j+w]);//动态转移
     }last=1;
    r(i,1,n)
    {
        read(now);b=now;//用b保存now，因为now要减去上次遗留的声音
        if(last)now-=last-1;//减去上次声音，-1是因为声音传到下一个农场音量变少了
        ans+=f[now];//累计答案
        last=b;//遗留声音
    }
    printf("%d",ans);
}