Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA.............求测试用例//将左边的和加上100000个单位,用背包求解,最后再减去100000输出 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define N 200010 #define INF (1<<31) int bag[N]; int main(){ int n, i, j, k; int a, b; int max; scanf("%d",&n); bag[100000] = 0; k = n; for(i = 0; i < N; i++) bag[i] = -INF; while (k--){ scanf("%d %d", &a, &b); if(a <= 0 && b <= 0) continue; if(a < 0) for(i = 0; i < N; i++) { if(bag[i] == -INF) continue; if(bag[i]+b > bag[i+a]) bag[i+a] = bag[i]+b; } else for(i = N; i >= 0; i--) { if(bag[i] == -INF) continue; if(bag[i]+b > bag[i+a]) bag[i+a] = bag[i]+b; } if(bag[100000+a] < b) {bag[100000+a] = b;} } max = -INF; for(i = 100000; i < N; i++) if(bag[i] <= 0) continue; else if(max < bag[i]+i) max = bag[i]+i; max = max - 100000; printf("%d\n",max); system("pause"); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator