参考与:http://blog.csdn.net/actangy/article/details/7433992
题意:给出n个 si 和 fi , 要求si和fi的和 都不能是负数的前提下,求Σsi+Σfi的最大和。
思路:见参考。。。我是弱B。。。╮(╯▽╰)╭
#include<iostream> #include<cstdio> #include<cstring> #define inf 10000000 using namespace std; const int maxn = 200010; int dp[maxn]; int si[105] , fi[105]; int main() { int n , i , j; while(~scanf("%d",&n)) { for(i = 0 ; i < n ; i ++) scanf("%d%d",&si[i],&fi[i]); for(i = 0 ; i < maxn ; i ++) dp[i] = -inf; dp[100000] = 0;// 装满背包 for(i = 0 ; i < n ; i ++) { if(si[i] > 0) { for(j = 200000 ; j >= si[i] ; j --) dp[j] = max(dp[j] , dp[j - si[i]] + fi[i]); } else { for(j = 0 ; j - si[i]<= 200000 ; j ++) dp[j] = max(dp[j] , dp[j - si[i]] + fi[i]); } } int ans = 0; for(i = 100000 ; i <= 200000 ; i ++) if(dp[i] >= 0) ans = max(ans , dp[i] + i - 100000); printf("%d\n",ans); } }