Code 備忘錄►DP

STEP5::Problem 0130 : 壓力好大

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0130
這題是01背包問題的變形。先開一個寬度跟體力一樣陣列，每個元素初始成你銀行裡的錢，把任務依照賺的錢排序(得到-花費)，然後 DP[i]=MAX(DP[i],DP[i-體力]+得到-花費)。
注意DP順序要從後面跑到前面，不然會一個任務做兩次。最後輸出 DP[體力]那個。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 5001
using namespace std;

int ci[N],ai[N],pi[N],bapk[N];

void quickSort(int A[],int B[],int C[],int left, int right)
{
    int i, j, s , Temp;
    if(left < right) {
        s = A[(left+right)/2];
        i = left - 1;
        j = right + 1;
        while(1) {
            while(A[++i] < s) ;  // ¦V¥k§ä
            while(A[--j] > s) ;  // ¦V¥ª§ä
            if(i >= j) break;
               Temp = A[i];
               A[i] = A[j];
               A[j] = Temp;
               Temp = B[i];
               B[i] = B[j];
               B[j] = Temp;
               Temp = C[i];
               C[i] = C[j];
               C[j] = Temp;
        }
        quickSort(A,B,C, left, i-1);   // ¹ï¥ªÃä¶i¦æ»¼°j
        quickSort(A,B,C, j+1, right);  // ¹ï¥kÃä¶i¦æ»¼°j
    }
}

void work(int i,int p)
{
    if (p == 0)return;
    if (pi[i] > p)return;
    if (bapk[p- pi[i]] >= ci[i])
            bapk[p] = ( bapk[p]> bapk[p- pi[i]]+ ai[i])? bapk[p]: bapk[p- pi[i]]+ ai[i];
    work (i, p-1);
}

int main(int argc,char *argv[])
{
    int n,c,p;
    scanf ("%d %d %d", &n, &c, &p);
    for (int i=1; i<=n; i++){
            scanf ("%d %d %d", &ci[i], &ai[i], &pi[i]);
            if(ai[i]- ci[i]> 0) 
                     ai[i] -= ci[i];
            else {
                     i--;
                     n--;
            }
    }
    for (int i=1; i<=n; i++)
            bapk[i]= i;
    quickSort (ci, ai, pi, 1, n);
    for (int i=0; i<p; i++)
            bapk[i]= c;
    for (int i=1; i<=n; i++)
            work (i, p);
    printf ("%d\n", bapk[p-1]);
    return 0;
}