背包DP

- P2340 [USACO03FALL] Cow Exhibition G

• 思路：

我们发现，跟状态有关的三个值：\(S\) , \(F\) , \(S+F\)，我们只需要知道其中的两个就可以推出剩下一个，所以，我们可以选其中一个做体积，一个做价值，跑一遍 \(01\)背包即可。

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
inline ll rd(){
	ll x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9'){
		x=1ll*x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n;
struct cow{
	int a,b;
}c[450];
ll sum[1800002];
void init(){
	n=rd();
	for(int i=1;i<=n;i++) c[i].a=rd(),c[i].b=rd();
}
void solve(){
    memset(sum,-0x3f,sizeof sum);
    sum[400000]=0;
	for(int i=1;i<=n;i++){
		if(c[i].a>=0){
            for(int j=800000;j>=c[i].a;j--){
                sum[j]=max(sum[j],sum[j-c[i].a]+c[i].b);
            }
        }
        else{
            for(int j=0;j<=800000+c[i].a;j++){
                sum[j]=max(sum[j],sum[j-c[i].a]+c[i].b);
            }
        }
	} 
}
void print(){
	ll maxx=-1e8;
	for(int i=400000;i<=800000;i++)
        if(sum[i]>=0)
            maxx=max(maxx,sum[i]+i-400000);
	cout<<maxx;
}
signed main(){
	init();
	solve();
	print();
}