牛客小白赛 18 J： Forsaken喜欢玩自走棋（SOS DP）

对于一个二进制，它的贡献必须加到它的子集里，这和SOS DP 的形式类似。

把每个输入的进制取反，整个过程也就反过来了：一个二进制，它的贡献必须加到包含它的集合里，即求子集和，这正是SOS DP的过程。

于是求一遍SOS DP，遍历 $2^{20}$ 以内的二进制，找出值最大二进制值也最大的即可。

SOS DP （子集和DP）是类似高维前缀和的东西，由于它每一位只有0和1，它的高维前缀和就等于它的子集和。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int n;
ll dp[1 << 21];
int main() {scanf("%d",&n);int tot = 1 << 20;for(int i = 1; i <= n; i++) {int s,v;scanf("%d%d",&s,&v);s ^= (tot - 1);dp[s] += v;}for(int i = 0; i < 20; i++)for(int j = 0; j < tot; j++)if(j >> i & 1) dp[j] += dp[j ^ (1 << i)];ll mx = -1e18;int res = -1;for(int i = 0; i < tot; i++) {if(dp[i] > mx) {mx = dp[i];res = i;} else if(dp[i] == mx) {res = max(res,i);}}printf("%d %lld\n",(tot - 1) ^ res,mx);return 0;
}