Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WA.............求测试用例

Posted by xiakk0 at 2010-08-12 13:33:22 on Problem 2184
//将左边的和加上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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator