P15491 [IOI 2004] Farmer

Nostopathy · 2026-02-28 09:25:13 · 题解

只有选择完整的环，才能使点和点之间的间隔数量相等，即得到于柏树数量相等的橄榄树。否则只能得到比柏树数量少一棵的橄榄树。

故优先选择所有完整环，如果能选恰好 Q 棵柏树，则答案为 Q，这是一个完全背包问题。

若不能选出恰好 Q 棵，考虑从这些环里选一个变成链，则答案为 Q-1。

为什么只需选一个：可以从最长的环开始尝试变成链，并逐渐累加长度，由于环长度至少为 3，一定能找到第一个总和不小于 Q 的位置，将最后的环变链即可。

若 Q > \sum_{i=1}^M N_i，则多出的部分需要用链。由于不论如何截取一段链，得到的橄榄树数量总比选择的柏树数量少一棵，而想要损失最小，故贪心地选择最长的几条链。

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

const int N = 2005;

int q, m, k, s;
int n[N], r[N];
bitset<150005> bs;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> q >> m >> k;
    bs[0] = 1; // 初始化
    for(int i = 1; i <= m; ++ i){
        cin >> n[i];
        bs |= (bs << n[i]); // bitset 求完全背包
        s += n[i];
    }
    for(int i = 1; i <= k; ++ i)
        cin >> r[i];

    if(bs[q]) return cout << q, 0;
    if(q <= s) return cout << q - 1, 0;

    sort(r + 1, r + k + 1, greater<int>());
    int i, q1 = q;
    for(i = 1; q - s > 0; ++ i)
        q -= r[i];
    cout << q1 - i + 1; // for 循环最后会 i 多加一次，答案要加回来

    return 0;
}