「JoyOI1089」smrtfun

2014年1月23日2,9530

题目描述

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

样例输入

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

样例输出

提示

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

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,f[101][200001];//前i个数sum_a[i]为j的max{sum_b[i]}
int ans,maxa=100000,mina=100000;
int a[1001],b[1001];
int main()
{

    scanf("%d",&n);
    for(int i=0;i<=n;i++)
       for(int j=0;j<=200000;j++)
          f[i][j]=-999999;
    f[0][100000]=0;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i<=n;i++)
    {
       maxa=max(maxa,maxa+a[i]);
       mina=min(mina,mina+a[i]);
       for(int j=200000;j>=0;j--)
          {
               f[i][j]=max(f[i][j],f[i-1][j]);
               if(j-a[i]>=0)f[i][j]=max(f[i][j],f[i-1][j-a[i]]+b[i]);
               if(j>=100000&&f[i][j]>=0)ans=max(ans,j+f[i][j]-100000);
               }
    }
    printf("%d",ans);
    return 0;
    }

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,f[101][200001];//前i个数sum_a[i]为j的max{sum_b[i]}

int ans,maxa=100000,mina=100000;

int a[1001],b[1001];

int main()

{

scanf("%d",&n);

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

for(int j=0;j<=200000;j++)

f[i][j]=-999999;

f[0][100000]=0;

for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);

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

{

maxa=max(maxa,maxa+a[i]);

mina=min(mina,mina+a[i]);

for(int j=200000;j>=0;j--)

{

f[i][j]=max(f[i][j],f[i-1][j]);

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

if(j>=100000&&f[i][j]>=0)ans=max(ans,j+f[i][j]-100000);

}

printf("%d",ans);

return 0;

}

« 「vijos1153」猫狗大战「JoyOI1087」sumsets »

hzwer.com _ Home | http://hzwer.com

「JoyOI1089」smrtfun

题目描述

输入

输出

样例输入

样例输出

提示

代码

分类目录

热门文章

Myfriends

近期评论