ZOJ 3264 Present for MM

テーマの説明:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3566
問題解決の考え方:
リュックサックのような問題です.研究したことがありません.とりあえず私はこうしました.dp[w]には重さがあります.wの下で最大のvはdp[w-1]からdp[w]に押されていません.
重さを加えるたびに処理します.実は、1、2、3の3つの状況は全部元のdp[]に変えてw 1、v 1、w 2を挿入します.
v 2、その中の第一の種類は(w 1+w 2、v 1+v 2)で、(w 1、0)、(w 2、0)の三種類の場合、彼らの値をt[]に預けて、一番大きいのを取って最後にdp[]に入れます.二番目です
つまり(w 1、v 1)、(w 2、v 2)の2つの場合のスクリーニングです.第三の種類は(w 1,v 1)、(w 1+w 2,v 1+v 2)です.
最後に巡回します.一番大きいのは答えです.
コード:

 1 #include <iostream>

 2 #include <stdlib.h>

 3 #include <string>

 4 #include <cstring>

 5 using namespace std;

 6 int N ;

 7 int t[50001];

 8 int dp[50001];

 9 void insertValue(int w1, int v1, int w2, int v2)

10 {

11     int i, j;

12     memset(t, -1, sizeof t);

13     for(i = 0; i < N; i ++)

14         if(dp[i] != -1 && i + w1 < N)

15             t[i+w1] = dp[i] + v1;

16     if(v2 != 0) 

17     {

18         for(i = 0; i < N; i ++)

19         {

20             if(dp[i] != -1 && i + w2 < N)

21             {

22                 int temp = v2 + dp[i];

23                 t[w2+i] = temp > t[w2+i] ? temp : t[w2+i];

24             }

25         }

26     }

27     for(i = 0; i < N; i ++)

28         dp[i] = t[i] > dp[i] ? t[i] : dp[i];     

29 }

30 int main()

31 {

32     int total, num;

33     int i, j;

34     int w1, v1, w2, v2, t;

35     while(cin >> total >> num)

36     {

37         total /= 100;

38         N = total + 5;

39         memset(dp, -1, sizeof dp);

40         dp[0] = 0;

41         for(i = 0; i < num; i ++)

42         {

43             cin >> w1 >> v1 >> w2 >> v2 >> t;

44             w1 /= 100;

45             w2 /= 100;

46             if(t == 1)

47             {

48                 w1 += w2;

49                 v1 += v2;

50                 v2 = 0;

51             }

52             else if(t == 3)

53             {

54                 w2 += w1;

55                 v2 += v1;

56             } 

57             insertValue(w1, v1, w2, v2);

58         }

59         int max = -1;

60         for(i = 0; i <= total; i ++)

61             max = max > dp[i] ? max : dp[i];

62         cout << max << endl;

63     }

64     return 0;

65 }