solution-p2214

luqyou · 2022-10-20 21:54:56 · 题解

直接上思路

首先，我们先把每个牧场实际的音量算出来：

m[i]=a[i]-(a[i-1]?a[i-1]-1:a[i-1]);

其中 a_i 为牧场总音量，m_i 为每个牧场实际发出的音量。

接着，由于我们考虑到每个牧场总音量不会超过 10^5，所以建立一个数组 f，其意义为当一个牧场的音量为 i 时，其牧场总至少有几头牛。

于是，我们便可以得到：

if(i<minn) f[i]=0; //这里是特判一头牛也放不了的情况
else{
    f[i]=2147483647;
    for(int j=1;j<=b;j++){
        if(i>=v[j]&&(f[i-v[j]]||i-v[j]==0)) f[i]=min(f[i],f[i-v[j]]+1);
    }
}
if(f[i]==2147483647) f[i]=0;

接下来，我们扫一遍我们算出来的实际音量，将结果使用 ans 累加：

for(int i=1;i<=n;i++){
        ans+=f[m[i]];
}

那么，这题就算做完了！最后，来贴一下完整代码。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,b,v[101],a[101],m[101],maxn=-1,minn=2147483647,f[100001],ans; 
int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=b;i++){
        scanf("%d",&v[i]);
        minn=min(minn,v[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m[i]=a[i]-(a[i-1]?a[i-1]-1:a[i-1]);
        maxn=max(maxn,m[i]);//提取实际音量的最大值，递推（DP）时递推到maxn即可               
    }
    for(int i=1;i<=maxn;i++){
        if(i<minn) f[i]=0;
        else{
            f[i]=2147483647;
            for(int j=1;j<=b;j++){
                if(i>=v[j]&&(f[i-v[j]]||i-v[j]==0)) f[i]=min(f[i],f[i-v[j]]+1);
            }
        }
        if(f[i]==2147483647) f[i]=0;
    }
    for(int i=1;i<=n;i++){
        ans+=f[m[i]];
    }
    printf("%d",ans);
    return 0;
}