[luogu] P1466 集合 Subset Sums 01背包求方案数

前言

新校区真好玩,(又得多补一一天的题O,O…

传送门 :

思路

其实这题一开始是直接想到 d f s dfs dfs 但是奈何不会优化, 还是走了 01 01 01背包方案数问题

显然这题是给你 n n n个数,然后你从中选取任意个使其等于 m / 2 m/2 m/2

这不就相当于自然数的拆分 那个题吗,所以我们只需要直接 d p dp dp 即可

但是这题有一点 c f cf cf的味道,需要特判奇偶,因为奇数不可以被分一半

code

typedef pair pii;
map mp;

const int N  = 1e4+10;
ll dp[N];
ll n,m;

void solve()
{
	cin>>n;
	m =  (n+1)*n /2;
	if(m&1){
		cout