小苯的粉丝关注

[题目链接](https://www.nowcoder.com/practice/697cf95e85cc4061b1d3429d39e00780)

思路

小苯有 $n$ 个旧账号，第 $i$ 个账号有 $a_i$ 个粉丝。他要让新账号恰好获得 $k$ 个粉丝。在第 $i$ 个旧账号发一次推荐文章，新账号涨粉 $\lfloor a_i / 2 \rfloor$ ；他还可以最多选择一个旧账号多次发推荐文章，该账号涨粉 $a_i$ （不取半）。求最少在几个旧账号发文。

问题转化

选择一个账号子集 $S$ ，从中至多挑一个账号 $j$ 获得 $a_j$ 的贡献，其余账号 $i \in S \setminus \{j\}$ 各贡献 $\lfloor a_i / 2 \rfloor$ 。要求总贡献恰好等于 $k$ ，最小化 $|S|$ 。

枚举 + 0-1 背包

由于 $n, k, a_i \le 100$ ，数据范围很小，可以枚举"哪个账号被选为多次发文的账号"（也可以不选），然后用 0-1 背包求剩余目标的最少物品数。

具体地，令 $b_i = \lfloor a_i / 2 \rfloor$ 。枚举 $j$ （ $j = -1$ 表示不选任何账号多次发文， $j = 0, 1, \ldots, n-1$ 表示选第 $j$ 个账号）：

计算剩余目标 $\text{target} = k - (j \ge 0\ ?\ a_j : 0)$ 。若 $\text{target} < 0$ ，跳过。
在 $\{b_i : i \ne j,\ b_i > 0\}$ 上做 0-1 背包： $dp[s]$ 表示恰好凑出和为 $s$ 所需的最少物品数。
若 $dp[\text{target}]$ 有解，则答案候选为 $dp[\text{target}] + [j \ge 0]$ 。

取所有候选的最小值即为答案。若无解，输出 $-1$ 。

样例演示

输入 $n=5,\ k=8$ ， $a = [1, 2, 3, 4, 10]$ ，对应 $b = [0, 1, 1, 2, 5]$ 。

选 $j=2$ （账号 3 多次发文，贡献 $a_2 = 3$ ），剩余目标 $= 8 - 3 = 5$ 。
在 $b = [0, 1, 2, 5]$ （去掉 $b_2$ ）中凑出 $5$ ，选 $b_4 = 5$ ，用 $1$ 个物品。
总计 $1 + 1 = 2$ 个账号，即为最优解。

复杂度分析

时间复杂度： $O(n^2 \cdot k)$ 。枚举 $j$ 共 $O(n)$ 轮，每轮做一次 $O(n \cdot k)$ 的 0-1 背包。
空间复杂度： $O(k)$ ，DP 数组大小。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    vector<int> b(n);
    for (int i = 0; i < n; i++) b[i] = a[i] / 2;

    int ans = INT_MAX;

    for (int j = -1; j < n; j++) {
        int target = k - (j >= 0 ? a[j] : 0);
        if (target < 0) continue;

        vector<int> dp(target + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (i == j || b[i] == 0) continue;
            for (int s = target; s >= b[i]; s--) {
                if (dp[s - b[i]] != INT_MAX) {
                    dp[s] = min(dp[s], dp[s - b[i]] + 1);
                }
            }
        }

        if (dp[target] != INT_MAX) {
            int cost = dp[target] + (j >= 0 ? 1 : 0);
            ans = min(ans, cost);
        }
    }

    printf("%d\n", ans == INT_MAX ? -1 : ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int[] b = new int[n];
        for (int i = 0; i < n; i++) b[i] = a[i] / 2;

        int ans = Integer.MAX_VALUE;

        for (int j = -1; j < n; j++) {
            int target = k - (j >= 0 ? a[j] : 0);
            if (target < 0) continue;

            int[] dp = new int[target + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;

            for (int i = 0; i < n; i++) {
                if (i == j || b[i] == 0) continue;
                for (int s = target; s >= b[i]; s--) {
                    if (dp[s - b[i]] != Integer.MAX_VALUE) {
                        dp[s] = Math.min(dp[s], dp[s - b[i]] + 1);
                    }
                }
            }

            if (dp[target] != Integer.MAX_VALUE) {
                int cost = dp[target] + (j >= 0 ? 1 : 0);
                ans = Math.min(ans, cost);
            }
        }

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
}