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

· · 题解

看似是dp实则是暴力，因为数据水所以过了

用一个dp数组储存所有声音大小最小的可能性，懒得优化，反正100000*100是可以刚好过的

然后用了一个倒序减去风吹因素的方法

#define oo 0x7f7f7f7f;//正无穷
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,b;
    cin>>n>>b;
    int v[b],field[n];

    int dp[100005];
    for(int i=0;i<100005;i++)   dp[i]=oo;//数组初始化，默认正无穷的
    for(int i=0;i<b;i++)    cin>>v[i];

    dp[0]=0;
    for(int i=0;i<100005;i++)
        for(int j=0;j<b;j++)
            if(i>=v[j])
                dp[i]=min(dp[i],dp[i-v[j]]+1);//无脑判小
    //这个dp数组存的是对于每一种音量，奶牛种类数的最小值
    for(int i=0;i<n;i++)    cin>>field[i];
    for(int i=n-1;i>0;i--)
        field[i]-=max(0,(field[i-1]-1));//倒序减去（上个田音量-1）

    int ans=0;
    for(int i=0;i<n;i++)
        ans+=dp[field[i]];//处理完field数组后，每一块田直接加上最小值

    cout<<ans<<endl;
    return 0;       
}

优化很烂的代码，只为了方便， 不建议模仿 ，不过读起来还挺舒服（表打我）