POJ 2184 Cow Exhibition

题目

◇题目传送门◆

题目大意

有$N$头奶牛，第$i$头牛的属性值为$s_i,f_i$，现要求选出一部分牛，使得其$s_i,f_i$的总和尽可能的大，且满足：$s_i$之和为非负数，$f_i$之和为非负数。若不满足条件，则输出0。

思路

这道题每头奶牛有两个值。直接计算可能不太好处理。我们可以考虑将$s$作为数组下标，$f$作为值来进行计算。就可以将这道题转化为01背包。

实现细节

读题我们可以发现，$s$值可能是负数，所以我们可以考虑坐标平移，即在计算时将$s$加上一个数，使得其值变为正数。

注意在计算时若遇到负的$s$，则应正着做循环；遇到正的$s$则应倒着做。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=100;
const int X=1000*100;
const int INF=0x3f3f3f3f;int N,s[Maxn+5],f[Maxn+5];
int dp[X*2+5];int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifmemset(dp,-0x3f,sizeof dp);dp[X]=0;scanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d %d",&s[i],&f[i]);for(int i=1;i<=N;i++) {if(s[i]<0&&f[i]<0)continue;if(s[i]<=0) {for(int j=0;j<=2*X+s[i];j++)dp[j]=max(dp[j],dp[j-s[i]]+f[i]);} else {for(int j=2*X;j>=s[i];j--)dp[j]=max(dp[j],dp[j-s[i]]+f[i]);}}int ans=-1;for(int i=X;i<=2*X;i++)if(dp[i]>=0)ans=max(ans,dp[i]+i-X);printf("%d\n",ans);return 0;
}