题目大意

题目链接

给你n个点，求满足所有x坐标之和为0， 所有y坐标之和为0， 的真子集的数量。

|x| <= 10, |y| <= 10, n <= 40

分析

唉， 愣是没想到用dp， 傻了吧唧的

设 dp[i][x][y] 为前i个点， x坐标值和为x， y坐标和为y的集合的数量。

dp[i][x][y] = dp[i - 1][x][y] + dp[i - 1][x - xi][y - yi]

可以滚动减少大量空间。

注意， x，y坐标之和最大为 400 最小为 -400， 我们设初始状态为 dp[0][400][400] = 1， 最终答案就是dp[0][400][400] 或者 dp[1][400][400]

这样 x，y坐标之和最大为 800 最小为 0。

当然你设成初始状态 dp[0][500][500] = 1也可以， 答案也会相应的改。

代码

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
/*
power by Solo_Dance
*/
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}

ll f[2][1005][1005];

int main(){
    int n = read();
    int flag = 0;
    f[0][400][400] = 1;
    for (int i = 1; i <= n; ++i){
        flag = !flag;
        int x = read(), y = read();
        for (int j = 0; j <= 1000; ++j){
            for (int k = 0; k <= 1000; ++k){
                f[flag][j][k] = f[flag ^ 1][j][k];
                if (j - x >= 0 && k - y >= 0 && j - x <= 1000 && k - y <= 1000)
                    f[flag][j][k] += f[flag ^ 1][j - x][k - y];
            }
        }
    }

    cout << f[flag][400][400] - 1 << "\n";

    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。