【题解】P1466

Qutam · 2020-02-16 09:22:04 · 题解

这题是一个背包板子。

对于只选前i项的数，它们的和正好是j的方案总数，我们可以这样想，先考虑第i个数选不选。所以方案总数就应该是选的方案和不选的方案之和。

状态转移方程为：

需要注意，有解的前提必须是数字之和是偶数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[40],dp[45][2010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        a[i]=i;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n*(n+1)/2;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];
        }
    if(n*(n+1)%4==0)cout<<dp[n][n*(n+1)/4]<<endl;
    else cout<<0<<endl;
    return 0;
}