【Tyvj1089】smrtfun

2014-05-25
竞赛题解 / 动态规划
TYVJ

描述 Description

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

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

20
312 -311
-316 317
-105 106
430 -429
-935 936
60 -59
656 -655
-287 288
505 -504
609 -608
818 -817
877 -876
78 -77
-564 565
-950 951
-443 444
650 -649
574 -573
-609 610
-75 76

样例输出 SampleOutput

17

Tyvj 1089

代码 Code

C++ 数组要用到负数下标的时候真是麻烦 = =

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define F(a) f[a+1000000]
#define inf 0x7fffffff/2711;
int a[1001],b[1001];
int f[10000001];
int i,j,t,n,m,l,r,k,z,y,x,ans,xmax,xmin;
int main()
{
    for (i=-1000000;i<=1000000;i++) F(i)=-inf;
    F(0)=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    ans=0;xmax=0;xmin=0;
    for (i=1;i<=n;i++)
    {
        if (a[i]>0)
        {
            xmax+=a[i];
            for (j=xmax;j>=xmin+a[i];j--)
            {
                F(j)=max(F(j-a[i])+b[i],F(j));
            }
        }
        else
        {
            xmin+=a[i];
            for (j=xmin;j<=xmax+a[i];j++)
            {
                F(j)=max(F(j-a[i])+b[i],F(j));
            }
        }
    }
    for (i=0;i<=xmax;i++) if (F(i)>=0) ans=max(ans,F(i)+i);
    printf("%d\n",ans+t);
    return 0;
}