USACO 2.2 Subset Sums-动态规划

题目描述

For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.

For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

{3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).

If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

  • {1,6,7} and {2,3,4,5}
  • {2,5,7} and {1,3,4,6}
  • {3,4,7} and {1,2,5,6}
  • {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.

Your program must calculate the answer, not look it up from a table.

PROGRAM NAME: subset

Solution

装箱问题:对于任意一个N,求能装满\(\frac{(1+2+3+…+N)}{2}\)的大小的背包的方案总数。

所以我们首先判断\(\sum_{i=1}^N i\)能否被2整除,不能显然没有可行方案。

然后考虑dp,设\( dp[i][j] \)为处理完 (1,i),总和为j的方案数,显然方程是\( dp[i][j] = dp[i][j] + dp[i - 1][j - i](j \geq i)\)

然后搞个滚动数组把i这个维度消掉即可

Code

/*
PROB: subset
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const int maxn = 10000 + 5;

LL n;
LL dp[maxn];

inline void Solve (){
    LL tmp = n * (n + 1) / 2;
    if(tmp % 2){
        printf("0\n");
        return;
    }
    tmp /= 2;
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = tmp; j >= i; j--){
            dp[j] += dp[j - i];
        }
    }
    printf("%lld\n",dp[tmp]/ 2);
}

inline void Input (){
    n = read<LL>();
}

int main(){
    Input();
    Solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注