原题 题目大意：一共有n头牛，每头牛都有个值s[i]，f[i]。请从中取一部分牛出来，使得这部分牛的s之和S不为负数，f之和F不为负数，且此时的S+F最大，请输出S+F的值。
解题思路：是后来看博客补的，这里使用的是dp的解法，不过，这里dp[i]，i储存的是s[i]当前的总和。 所以，这样dp表达式很容易就可以出来dp[i]=max(dp[i],dp[i-s[j]]+f[j]) 但是重点的不是这个，是次序，因为每个牛只能使用一次，所以s[i]是正是负的顺序是不一样的，其实都是为了保证最新得到的dp不会受到此次dp之前的任何dp的影响(因为已经更新过的dp都受到了这头牛的影响，而一头牛只可以影响一次)。
注意： 1：当s[i]和f[i]都是负数时，直接continue，没什么好说的 2：更新当前的dp的前提时该dp曾经被用过， 3: 为了得到负数，可以把0节点往前推，使得dp[100000]=0;
#include<cstdio> #include<iostream> using namespace std; const int MX=2e5+9; const int inf=0x3f3f3f3f; int dp[MX+1],n,s[MX],f[MX]; int main() { freopen("input.txt","r",stdin); while( ~scanf("%d",&n) ){ for( int i=1 ; i<=n ; i++ ) scanf("%d %d ",&s[i],&f[i]); for( int i=0 ; i<=MX ; i++ ) dp[i]=-inf; dp[100000]=0; for( int i=1 ; i<=n ; i++ ){ if( s[i]<=0 && f[i]<=0 ) continue; if( s[i]>0 ){ for( int j=MX ; j>=s[i] ; j-- ) // 最新的dp不会受到刚刚dp完的影响 if( dp[j-s[i]]>-inf ) // 使用这个dp一定要这个dp曾经被使用过 dp[j]=max(dp[j],dp[j-s[i]]+f[i]); } else { for( int j=s[i] ; j<=MX+s[i] ; j++ ) // 同上 if( dp[j-s[i]]>-inf ) dp[j]=max(dp[j],dp[j-s[i]]+f[i]); } } int ans=-inf; for( int i=100000 ; i<=MX ; i++ ) if( dp[i]>=0 ) // 因为s的总和大于等于0，f的总和也要大于等于0，所以dp必须取>=0的， ans=max(ans,i-100000+dp[i]); printf("%d\n",ans); } return 0; }