USACO03FALL-Cow Exhibition G

[USACO03FALL]Cow Exhibition G

题意

给定 $n$ 个数分别有 $2$ 个权值 $a_i,b_i$，选取一些数使得 $\sum a_i\geq 0,\sum b_i\geq 0$ 的条件下求 $\sum a_i+b_i$ 的最大值。

Sol

我们考虑将 $dp_i$ 表示 $\sum a_i$ 为 $i$ 时 $\sum b_i$ 的最大值。

此时我们进行 01 背包，最后统计答案为 $\max\{i+dp_i\}_{i\geq 0}$，注意处理数组为负。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,Tp=4e5,MAXN=Tp+Tp+10;
const lint INF=1e18+1e9;

lint dp[MAXN<<1],Ans=0;
int n;

int main(void){

	scanf("%d",&n);
	memset(dp,128,sizeof(dp)),dp[Tp]=0;
	for(int i=1;i<=n;i++){
		lint a=readlint,b=readlint;
		if(a>0) for(int j=Tp;j>=a-Tp;j--) dp[j+Tp]=max(dp[j-a+Tp]+b,dp[j+Tp]);
		else for(int j=-Tp;j<=Tp+a;j++) dp[j+Tp]=max(dp[j-a+Tp]+b,dp[j+Tp]);
	}
	for(int i=0;i<=Tp;i++) if(dp[i+Tp]>=0) Ans=max(i+dp[i+Tp],Ans);
	printf("%lld\n",Ans);

	return 0;
}