USACO Section 2.2: Subset Sums
9284 ワード
dp問題、dpに出会うと私は基本的にひざまずいて、ネット上の答えを探して2種類に分けて、1次元と2次元.
まず2次元について,sum[i][j]は前i個数のsubsetにおける差分値jの分法数を表す.数値iを加えると、あるsetと別のsetの2つの選択肢があり、そのうちの1つの総和の大きいsetを加えると、新しい差はj+iであり、総和の小さいsetを加えると、新しい差はabs(j-i)である.
一元の考え方はsum[i]が総和iを表すset数である.
まず2次元について,sum[i][j]は前i個数のsubsetにおける差分値jの分法数を表す.数値iを加えると、あるsetと別のsetの2つの選択肢があり、そのうちの1つの総和の大きいsetを加えると、新しい差はj+iであり、総和の小さいsetを加えると、新しい差はabs(j-i)である.
1 /*
2 ID: yingzho1
3 LANG: C++
4 TASK: subset
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16
17 using namespace std;
18
19 ifstream fin("subset.in");
20 ofstream fout("subset.out");
21
22 int N, s1, s2, acount;
23 int sum[40][1000];
24
25 int main()
26 {
27 fin >> N;
28 sum[1][1] = 1;
29 for (int i = 2; i <= N; i++) {
30 for (int j = 0; j < 781; j++) {
31 sum[i][j+i] += sum[i-1][j];
32 sum[i][abs(j-i)] += sum[i-1][j];
33 }
34 }
35 fout << sum[N][0] << endl;
36
37 return 0;
38 }一元の考え方はsum[i]が総和iを表すset数である.
1 /*
2 ID: yingzho1
3 LANG: C++
4 TASK: subset
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16
17 using namespace std;
18
19 ifstream fin("subset.in");
20 ofstream fout("subset.out");
21
22 int N;
23 long long sum[1000];
24
25 int main()
26 {
27 fin >> N;
28 int part = (N+1)*N/2;
29 if (part & 1) {
30 fout << 0 << endl;
31 return 0;
32 }
33 part /= 2;
34 sum[0] = 1;
35 for (int i = 1; i <= N; i++) {
36 for (int j = part; j >= i; j--) {
37 sum[j] += sum[j-i];
38 }
39 }
40 fout << sum[part]/2 << endl;
41
42 return 0;
43 }