tyvj[1089]smrtfun

时间：2024-06-29 20:05:20

描述

 现有N个物品，第i个物品有两个属性A_i和B_i。在其中选取若干个物品，使得sum{A_i + B_i}最大，同时sum{A_i}，sum{B_i}均非负（sum{}表示求和）。

输入格式

    第一行，一个整数，表示物品个数N。
    接下来N行，每行两个整数，表示A_i和B_i。

输出格式

一个整数，表示最大的sum{A_i + B_i}。

测试样例1

输入

-

 -

 - 

- -

输出











备注


 N <= 100 , |A_i| <= 1000 , |B_i| <= 1000




题解


由于题目有∑a[i]>0且∑b[i]>0的限制，不能直接将i的价值处理为a[i]+b[i]的值并贪心挑选，只能用动态规划


用f[i][j]表示前i个物品∑a[i]=j时，∑b[i]的最大值


考虑a[i],b[i]>0的情况，直接用方程f[i][j]=max{f[i-1][j-a[i]]+b[i]}转移即可


由于题目中的a[i],b[i]∈[-1000,1000]，要将所有a及j向数轴正方向移动1000*100的距离，令下标j满足恒为正


因为考虑到f[i][]仅和f[i-1][]有关，可以用滚动数组优化空间（继续100*200000的空间也可以过）




#include<cstring>

#include<iostream>

#define N 100

#define D 100000

using namespace std;

int n,a[N|],b[N|],f[N][D<<|],ans,c;

int main(){

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=;i<=n;i++)

        cin>>a[i]>>b[i];

    memset(f,-,sizeof(f));

    f[][D]=;

    for(int i=;i<=n;i++){

        c^=;

        for(int j=D<<;j>=;j--)

            f[c][j]=f[c^][j];

        for(int j=D<<;j>=;j--){

            if(j>=a[i])f[c][j]=max(f[c][j],f[c^][j-a[i]]+b[i]);

            if(j>=D&&f[c][j]>=)ans=max(ans,j-D+f[c][j]);

        }

    }

    cout<<ans<<endl;

    return ;

}


相关文章