P2214 题解

huayt · 2022-07-01 11:10:34 · 题解

分析

这道题可以转化为完全背包，设当前位置为 i，音量为 d_i。

若 d_{i-1}=0，说明上个位置没有传过来音量，当前位置多出的音量为 d_i。

否则，当前位置多出的音量为 d_i-(d_{i-1}-1)。

特别的，当 i=1 时，当前位置多出的音量为 d_i。

把当前位置多出的音量当做背包容量，设第 i 种奶牛的音量为 v_i，f_j 表示容量为 j 时填充的最小奶牛数量。

得到状态转移方程如下：

• f[j]=\min(f[j],f[j-v[i]]+1)

每个位置跑一次背包，答案累加即可。

若存在某个位置没有答案，则输出 \texttt{-1}。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int v[21],f[N],sumV,ans;
int n,b;

int main(){
    int i,j,k;
    scanf("%d%d",&n,&b);
    for(i=1;i<=b;i++) scanf("%d",&v[i]);
    int tmp=0;//记录上个位置的音量
    for(i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        sumV=0;
        if(tmp==0) sumV=x;
        else if(tmp-1<x) sumV=x-(tmp-1);
        tmp=x;
        for(j=1;j<=sumV;j++) f[j]=INF;
        f[0]=0;//记得初始化
        for(j=1;j<=b;j++)
            for(k=v[j];k<=sumV;k++)
                f[k]=min(f[k],f[k-v[j]]+1);//完全背包
        if(f[sumV]==INF){
            printf("-1\n");
            return 0;
        }
        ans+=f[sumV];
    }
    printf("%d\n",ans);
    return 0;
}