P2214题解

Nuyoah_awa · 2023-04-15 20:14:46 · 题解

题目大意

有 B 种牛，每种牛的叫声为 V_i，每个农场听到的声音为 x，求 FarmerJohn 的农场里最少有几头奶牛。

题目分析

看到 B 种奶牛，n 个农场，就想到很像完全背包。所以这道题可以用 DP 做。

我们定义 dp[i] 为 农场中有 i 的声音，最少的奶牛数。

对于每种叫声为 v[j] 的奶牛，声音为 i 的农场的转移方程为：

知道声音为 i 的农场中最少的奶牛数后，我们就可以贪心求解了。

code

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5, INF = 1e9;
int f[N + 5], v[N + 5], n, b, u, now, ans;
int main()
{
    scanf("%d %d", &n, &b);
    for(int i = 0;i <= N;i++)
        f[i] = INF;
    f[0] = 0;
    for(int i = 1;i <= b;i++)
    {
        scanf("%d", &v[i]);
        for(int j = v[i];j <= N;j++)
            f[j] = min(f[j], f[j - v[i]] + 1);
    }
    for(int i = 1, x;i <= n;i++)
    {
        scanf("%d", &x);
        x -= now, now += x;
        now -= now ? 1 : 0;
        if(x < 0)
        {
            printf("-1");
            return 0;
        }
        if(f[x] == INF)
        {
            printf("-1");
            return 0;
        }
        ans += f[x];
    }
    printf("%d", ans);
    return 0;
}