hdu 5616 Jam's balance正逆リュック+変換
5941 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=5616
構想
題目には計算すべき二つの重さが含まれている.
1.すべての分銅から任意の種類を選び出す2.(転換の思想)天秤の両端にこれらの分銅の一部を選び出し、出張値を計算することもでき、この差も重量である これは実は1種の変換で、以下のこの公式(左端の分銅の重量)=(右端の分銅の重量+計算できる重量G)を見ます 分銅を初めて選択すると,第2の方法での重量Gを計算し,trueとしても記述し,また 新しい重量を更新し続け、G(新しい左端分銅重量)=(右端分銅の重量+算出できる重量) では、上記の過程はリュックサックから物を取り出す過程です. コードに詳細な分析があります.リュックサックを裏返しにする
コード:
構想
題目には計算すべき二つの重さが含まれている.
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 }