Description
有一个长度为\(n\)的数组为\(1-n\),求有多少种选择方案使得选择数之和等于序列和的一半
Solution
题面翻译成这样是不是就好做了？
首先，序列和的一半我们可以计算出\(n\times(n+1)\div 2 \div 2\),显然序列和的一半只有是整数才有解，如果不是整数直接输出0即可。
将题面转移成这样，是不是有点dp的性质！子结构之间可以互相转移，考虑dp
先设计状态：\(f_{i,j}\)表示前\(i\)位总和为\(j\)的方案数。状态转移方程：\(f_{i,j}+=f_{i-1,j-i}\)
和01背包同理，容易发现第\(i\)位只是和第\(i-1\)位有关联，所以可以压缩掉这一维状态。
但是压缩后，对于总和我们需要从大到小枚举，若从小到大枚举则和完全背包一样每个数可以被选多次，不符合题意。
本题关键在于将原始题面转换为可以被状态转移的题面，设计状态进行dp。
PS:像这种输出结果只有一位的题目这不就是让你打表送分的吗！！
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100010
#define int long long
using namespace std;
int n;
int f[N];
signed main()
{
scanf("%lld",&n);
int m = n*(n+1)/2;
if(m%2 != 0)
{
cout<<"0"<<endl;
return 0;
}
m/=2;
f[0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=i;j--) f[j] += f[j-i];
}
cout<<f[m]/2<<endl;
return 0;
}