| ||||||||||
| 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