题目大意 题目链接
给你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 #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
千万不要图快——如果没有足够的时间用来实践, 那么学得快, 忘得也快。