USACO 2.2.2: Subset Sums(DP)


题意

洛谷 P1466 集合 Subset Sums

将1到N的整数分成两个和相同的集合,问有多少种分法?

分析

这道题其实是一道标准的经典DP(只要正确建模)。结果我一看数据范围只有39,第一反应是写了一个Meet-in-the-Middle出来。当然也不是不行……

DP的做法是这样的:把原问题换成,用1到N的整数之和表示某个数字,最多有多少种表示方法?然后思路就很简单了,用f[i][j]表示用前i个整数表示j的方法,f[i][j] = f[i-1][j] + f[i-1][j-i]

然后我才意识到对N大小的限制主要是为了动态规划的其中一维不要太大……

代码

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
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int N;
LL f[40][8000];

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
f[0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 8000; j++) {
f[i][j] = f[i-1][j];
if (j >= i)
f[i][j] += f[i-1][j-i];
}
}
fout << f[N][sum / 2] / 2 << endl;
return 0;
}

Meet-in-the-Middle

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
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
int N;
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
int halfSum = sum / 2;
int halfN = N / 2;
// Meet-in-the-Middle
map<int, int> cntMap;
// gather [1, halfN] sums
for (int i = 0; i < (1 << halfN); i++) {
int sum = 0;
for (int j = 0; j < halfN; j++)
if (i & (1 << j))
sum += j + 1;
// cout << i << ' ' << sum << endl;
cntMap[sum]++;
}
// gather [halfN+1, N] sums
LL ans = 0; // 注意数据范围……
for (int i = 0; i < (1 << (N - halfN)); i++) {
int sum = 0;
for (int j = 0; j < N - halfN; j++)
if (i & (1 << j))
sum += j + halfN + 1;
if (cntMap.find(halfSum - sum) != cntMap.end()) {
ans += cntMap[halfSum - sum];
}
}
fout << ans / 2 << endl;
return 0;
}

 评论