AcWing 1365. 子集的和——暴力和动态规划双解法
原题链接
中等
作者:
虹之间
,
2020-12-25 19:15:34
,
所有人可见
,
阅读 740
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int solve(vector<int> &a){
int n = a.size();
int sum = 0;
for(auto num: a) sum += num;
if(n <= 1 || (sum & 1)) return 0;
vector<int> b, c;
int mid = n / 2;
for(int i = 0; i < mid; i ++ ) b.push_back(a[i]);
for(int i = mid; i < n; i ++ ) c.push_back(a[i]);
unordered_map<int, int> cntb, cntc;
for(int s = 0; s < (1 << b.size()); s ++ ){
int cur = 0;
for(int i = 0; i < b.size(); i ++ ){
if(s >> i & 1) cur += b[i];
}
cntb[cur] ++ ;
}
for(int s = 0; s < (1 << c.size()); s ++ ){
int cur = 0;
for(int i = 0; i < c.size(); i ++ ){
if(s >> i & 1) cur += c[i];
}
cntc[cur] ++ ;
}
long long res = 0;
for(pair<int, int> p : cntb) res += p.second * cntc[sum / 2 - p.first];
return res / 2;
}
int solve2(vector<int> &a){
int n = a.size();
int sum = 0;
for(auto num: a) sum += num;
if(n <= 1 || (sum & 1)) return 0;
sum /= 2;
vector<vector<long long>> dp(n + 1, vector<long long>(sum + 1, 0));
dp[0][0] = 1;
for(int i = 1; i <= n; i ++ ){
for(int j = 0; j <= sum; j ++ ){
if(j < a[i - 1]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]];
}
}
return dp[n][sum] / 2;
}
int main(int argc, char const *argv[])
{
int n; cin >> n;
vector<int> a;
for(int i = 1; i <= n; i ++ ) a.push_back(i);
cout << solve(a) << endl; // 暴力
// cout << solve2(a) << endl; // 转化为背包
return 0;
}