HDU 1574 RP 문제 (01 가방 변형)

전송:http://blog.csdn.net/mnlm1991/article/details/6083262
질문
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 959 Accepted Submission(s): 353
Problem Description
인류 사회 에서 모든 개체 가 인성 을 가지 고 인성 은 여러 가지 다른 형식 이 있 기 때문에 한 가지 형식 에서 다른 형식 으로 전환 할 수 있다. 한 개체 에서 다른 개체 에 게 전달 할 수 있다. 전환 과 전달 과정 에서 인성 은 사라 지지 않 고 창조 되 지 않 는 다. 이것 이 바로 '인성 보존 법칙' 이다.
인품 보존의 법칙 에 대한 더욱 형상 적 인 묘 사 는 좋 은 일이 발생 하면 그 중에서 이익 을 얻 으 면 반드시 일 정량의 RP 를 소모 한다.불행 한 일이 발생 하면 그 중 에 손실 이 있 으 면 반드시 일 정량의 RP 를 모 을 것 이다.
한 시간 안에 N 개의 사건 이 발생 할 수 있다 고 가정 하면 모든 사건 은 하나의 RP 변화 값 a, RP 문턱 값 b 와 수익 값 c 에 대응 합 니 다.RP 변화 값 a 가 플러스 이 고 수익 값 c 는 반드시 마이너스 입 니 다. 현재 RP 값 이 RP 문턱 값 b 보다 작 을 때 만 이 사건 이 발생 할 수 있 습 니 다. 이 사건 이 발생 할 때 RP 값 은 | a | 증가 하고 수익 값 은 | c | 감소 합 니 다.반대로, RP 변화 값 a 가 마이너스 이 고, 수익 값 c 는 반드시 플러스 입 니 다. 현재 RP 값 이 RP 문턱 값 b 보다 클 때 만 이 사건 이 발생 할 수 있 습 니 다. 이 사건 이 발생 할 때, 당신 의 RP 값 은 | a | 감소 하고, 수익 값 은 | c | 증가 합 니 다.
하나의 사건 이 상기 RP 조건 을 만족 시 키 는 전제 에서 반드시 발생 하 는 것 은 아니다.만약 에 이 시간 전에 당신 이 가지 고 있 는 RP 값 과 수익 값 이 모두 0 이 라 고 가정 하면 이 시간 이 지나 면 당신 이 달성 할 수 있 는 최대 수익 치 는 얼마 입 니까?
주의: 한 사람의 RP 값 은 마이너스 일 수 있 습 니 다.
Input
데 이 터 를 입력 하 는 첫 번 째 행 위 는 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.각 그룹의 테스트 데이터 의 첫 번 째 행동 은 정수 N (0 < N < = 1000) 입 니 다. 이 시간 대 에 당신 에 게 N 개의 사건 이 발생 할 수 있 음 을 표시 합 니 다.다음 N 줄 은 각 줄 에 세 개의 정수 a, b, c (0 < = | a | < = 10, 0 < = | b | < = 10000, 0 < = | c | < = 10000) 가 있 습 니 다.이 N 개 사건 은 입력 선착순 으로 차례로 발생 했다.즉, i 줄 의 사건 이 먼저 발생 한 다음 에 i – j 줄 의 사건 이 발생 할 수 없다 는 것 이다.
Output
각 그룹의 입력 에 대응 하여 독립 된 줄 에 정 수 를 출력 하여 최대 이익 을 얻 을 수 있 음 을 표시 합 니 다.
Sample Input

   
   
   
   

    
    
    
    3
1
-1 0 1
2
10 200 -1
-5 8 3
3
-5 0 4
10 -5 -5
-5 5 10
   
   
   
   

Sample Output

   
   
   
   

    
    
    
    1
2
9
   
   
   
   

Author
lwg
Source
HDU 2007-1 Programming Contest 

/*
  ：01     
    ： N      ，     RP   a，     c。
     。        RP  b，RP      RP >=RP  ，
RP        RP<=RP  。             。
  N<= 1000 ,a<=10,b<=10000,c<=10000;           ，
                    ，           i    ，
      i – j    。  RP      0；
 
  ： DP 。            RP  ，
               RP     。
        （    ），     dp[20001];dp[j]  RP j - 10000; 
           ，          RP ；
*/
/* 
   
*/  
#include<cstdio>  
#include<cstdlib>  
#include<cmath>  
#include<cstring>  
#include<vector>  
#include<algorithm>  
#include<string>  
#include<map>  
#include<bitset>  
#include<queue>  
using namespace std;  
const int size = 20001;  
int dp[size];  //    10000 
int T;  
int N;  
bool visited[size];  
int main()  
{  
    scanf("%d", &T);  
    while (T--)  
    {  
        scanf("%d", &N);  
        int a, b, c;  
        int i;  
        int j;  
        memset(dp, 0, sizeof(dp));  
        memset(visited, 0, sizeof(visited));  
        dp[10000] = 0;  //         
        visited[10000] = true;  //  0       
        for (i = 0; i < N; i++)  
        {  
            scanf("%d%d%d", &a, &b, &c);  
            if (a > 0)//a  0 c   0  RP   RP      
            {  
                for (j = b + 10000; j >= 0; j--) //RP  B，    j     b 
                {  
                    if (visited[j])  //    j      
                    {   
                        if (!visited[j + a]) //           ，     
                        {  
                            dp[j + a] = dp[j] + c;  
                            visited[j + a] = true;  
                        }  
                        else   //         
                        {  
                            dp[j + a] =   
                            max(dp[j + a], dp[j] + c);  
                        }  
                    }  
                }  
            }  
            else if (a < 0)  //a<0  c>0     j      b,     
            {  
                for (j = b + 10000; j < size; j++)  
                {  
                    if (visited[j])  
                    {  
                        if (!visited[j + a])  
                        {  
                            dp[j + a] = dp[j] + c;  
                            visited[j + a] = true;  
                        }  
                        else   
                        {  
                            dp[j + a] =   
                            max(dp[j + a], dp[j] + c);  
                        }  
                    }  
                }  
            }  
        }  
        int ans = 0;  
        for (i = 0; i < size; i++)  
        {  
            if (visited[i] && dp[i] > ans)  
            {  
                ans = dp[i];  
            }  
        }  
        printf("%d
", ans);  
    }  
    return 0;  
}