hdu 5616 Jam's balance正逆リュック+変換

5941 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=5616
構想
題目には計算すべき二つの重さが含まれている.
1.すべての分銅から任意の種類を選び出す2.(転換の思想)天秤の両端にこれらの分銅の一部を選び出し、出張値を計算することもでき、この差も重量である    これは実は1種の変換で、以下のこの公式(左端の分銅の重量)=(右端の分銅の重量+計算できる重量G)を見ます    分銅を初めて選択すると,第2の方法での重量Gを計算し,trueとしても記述し,また    新しい重量を更新し続け、G(新しい左端分銅重量)=(右端分銅の重量+算出できる重量)    では、上記の過程はリュックサックから物を取り出す過程です.    コードに詳細な分析があります.リュックサックを裏返しにする
コード:
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define MAXN 2005
 7 using namespace std;
 8 int w[MAXN];
 9 bool dp[MAXN];//    ,    ,    
10 int main()
11 {
12     int t,n,q,k;
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d",&n);
17         for(int i = 0;i<n;i++)
18         {
19             scanf("%d",&w[i]);
20         }
21         memset(dp,false,sizeof(dp));
22         dp[0] = true;
23         //positive
24         //
25         for(int i = 0;i<n;i++)
26         {
27             //           ,j              
28             //j-w[i]           
29             for(int j = MAXN;j>=w[i];j--)
30             {
31                 dp[j]|=dp[j-w[i]];
32             }
33             
34             //     ,       !!
35             /*
36                   for(int j = 0;j<=MAXN-w[i];j++)
37                 {
38                     dp[j+w[i]]|=dp[j];
39                 }
40 41                               n w[i],        n ,    !
42             */
43         }
44         
45         //negative
46         //
47         for(int i = 0;i<n;i++)
48         {
49             //                          
50             //j           
51             //52             //                      (   )
53             //                      (         )
54             for(int j = 0 ; j<=MAXN-w[i] ; j++)
55             {
56                 dp[j]|=dp[j+w[i]];
57             }
58             
59              //     ,        !!
60             /*
61                   for(int j = MAXN-w[i];j>=0;j--)
62                 {
63                     dp[j-w[i]]|=dp[j];
64                 }
65 66                               n w[i],        n ,    !
67             */
68         }
69         scanf("%d",&q);
70         for(int i = 1;i<=q;i++)
71         {
72             scanf("%d",&k);
73             if(dp[k])
74                 printf("YES
"); 75 else 76 printf("NO
"); 77 } 78 } 79 return 0; 80 }