题解：P15491 [IOI 2004] Farmer

· · 题解

题意

题意简单，不解释。

思路

首先我们发现选田地的情况优于选条状土地的情况，柏树棵数相等的情况下可以多获得 1 棵橄榄树。所以只有在在田地选完之后才会考虑选条状土地。

所以我们对田地跑一遍 01 背包，如果 f_{q} = q，那就表明可以用田地凑出 q 棵柏树。此时一定为最优情况，答案为 q。

接下来我们发现如果

\sum_{i=1}^{m}{n_{i}} \gt q

的话不会选到条状土地。此时答案一定是前面选了若干田地，最后选了一块条状土地，答案为 q-1。

其余情况下田地一定选完了，剩余的柏树还能再选条状土地。田地总共能获得 f_{q} 棵橄榄树。

接下来，我们发现每多一块单独的条状土地，我们就会少一棵橄榄树，所以考虑让条状土地的块数最小。考虑贪心，先对 r 数组排序然后再依次考虑即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (2e3+5);
const int MAXQ = (2e5+5);
int q,m,k,n[MAXN],r[MAXN],f[MAXQ],s,ans,p;
bool cmp(int a,int b){
    return a > b;
}
int main(){
    cin>>q>>m>>k;
    for(int i = 1;i <= m;i++){
        cin>>n[i];
        s += n[i];
    }
    for(int i = 1;i <= k;i++){
        cin>>r[i];
    }
    for(int i = 1;i <= m;i++){
        for(int j = q;j >= n[i];j--){
            f[j] = max(f[j],(f[(j-n[i])]+n[i]));
        }
    }
    if(f[q] == q){
        ans = q;
    }
    else if(s > q){
        ans = (q-1);
    }
    else{
        ans = f[q];
        p = (q-s);
        sort((r+1),(r+k+1),cmp);
        for(int i = 1;(i <= k) && (p > 0);i++){
            if(p >= r[i]){
                ans += (r[i]-1);
                p -= r[i];
            }
            else{
                ans += (p-1);
                p = 0;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}