【USACO 2.2】Subset Sums (DP)

N (1 <= N <= 39),问有多少种把1到N划分为两个集合的方法使得两个集合的和相等。

如果总和为奇数，那么就是0种划分方案。否则用dp做。

dp[i][j]表示前 i 个数划分到一个集合里，和为j的方法数。

dp[i][j]=dp[i-1][j]+dp[i][j-i]

n 为 39 时，1 到 39 的和为 780，枚举 j 的时候枚举到 s/2，最后输出dp[n][s/2]/2。

http://train.usaco.org/usacoprob2?a=z5hb7MFUmsX&S=subset

/*

TASK: subset

LANG: C++

*/

#include<bits/stdc++.h>

int n;

int s,ans;

long long dp[][];

int main(){

    freopen("subset.in","r",stdin);

    freopen("subset.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)s+=i;

    dp[][]=;

    if(s%==)

    for(int i=;i<=n;i++){

        for(int j=;j<=s/;j++)

            dp[i][j]+=dp[i-][j]+(j>=i?dp[i-][j-i]:);

    printf("%lld\n",dp[n][s/]/);

}

巴特西

【USACO 2.2】Subset Sums (DP)

最新文章

热门文章