题解 P1910 【L国的战斗之间谍】

北海_Beihai · 2017-08-28 22:07:43 · 题解

看了看题解，大多数人都是用搜索的。然而本题正解是二维背包！！！

二维背包我就不多说了，大家应该都知道。（不知道的请参见《信息学奥赛一本通》P351）

既然怕被驳回，我还是简单地讲讲吧

递推式：f[j][k]=max(f[j-b][k-c]+a)

#include<bits/stdc++.h>
using namespace std;
int f[1010][1010];
int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        for(int j=m;j>=b;j--)                                     //以下3行是算法的核心
            for(int k=x;k>=c;k--)
                f[j][k]=max(f[j][k],f[j-b][k-c]+a);
    }
    cout<<f[m][x];
    return 0;
}