首页 > 代码库 > tyvj[1089]smrtfun

tyvj[1089]smrtfun

描述

 现有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

输入

5 -5 7 8 -6 6 -3 2 1 -8 -5

输出

8

备注

 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 100000using namespace std;int n,a[N|1],b[N|1],f[N][D<<1|1],ans,c;int main(){    ios::sync_with_stdio(false);    cin>>n;    for(int i=1;i<=n;i++)        cin>>a[i]>>b[i];    memset(f,-127,sizeof(f));    f[0][D]=0;    for(int i=1;i<=n;i++){        c^=1;        for(int j=D<<1;j>=0;j--)            f[c][j]=f[c^1][j];        for(int j=D<<1;j>=0;j--){            if(j>=a[i])f[c][j]=max(f[c][j],f[c^1][j-a[i]]+b[i]);            if(j>=D&&f[c][j]>=0)ans=max(ans,j-D+f[c][j]);        }    }    cout<<ans<<endl;    return 0;}

 

tyvj[1089]smrtfun