Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 9479 | Accepted: 3653 |
Description
Input
Output
Sample Input
5 -5 7 8 -6 6 -3 2 1 -8 -5
Sample Output
8
有点不好理解、- -
由于SWUST OJ 数据太水,因而乱写AC、受不了。 - -
还有一种做法就是将每个聪明指数+1000、然后、、受不了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f int n; int w[110]; int v[110]; int dp[200010]; int main() { int i,j,k=100000; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%d",&w[i],&v[i]); } for(i=0;i<=200000;i++) dp[i]=-INF; dp[k]=0; for(i=1;i<=n;i++) { if(w[i]>=0) //正的是逆序 { for(j=200000;j>=w[i];j--) if(dp[j-w[i]]>-INF) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } else //负的是顺序 { for(j=0;j<=200000+w[i];j++) if(dp[j-w[i]]>-INF) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } int ans=0; for(i=100000;i<=200000;i++) if(dp[i]>=0 && dp[i]+i-100000>ans) ans=dp[i]+i-100000; printf("%d\n",ans); } return 0; }
背包 [POJ 2184 SWUST OJ 145] Cow Exhibition
原文:http://www.cnblogs.com/hate13/p/4159454.html