hdu 5000 Clone(背包)

题目链接：hdu 5000 Clone

题目大意：DRD具有分身的能力，对于两个分身A和B来说，如果A的各个能力都强于B，那么B就无法生存，先给定DRD的n种能力的上限值，问最多有多少个克隆人可以共存。

解题思路：将n项能力值和相同的人算为一类克隆人，那么如果两个人处于同一类的话，一定是可以共存的，所以只要计算哪一类人的数量最多即可。所以用01背包直接搞起，但是因为答案要对1e9+7取模，所以必须知道和为多少的时候最优，很显然在sum/2的时候最优。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2005;
const int mod = 1e9+7;

int N, M, T[maxn], dp[maxn];

int solve (int n) {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int s = n; s > 0; s--) {
            for (int j = 1; j <= T[i] && j <= s; j++)
                dp[s] = (dp[s] + dp[s-j]) % mod;
        }
    }
    return dp[n];
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        M = 0;
        scanf("%d", &N);
        for (int i = 1; i <= N; i++) {
            scanf("%d", &T[i]);
            M += T[i];
        }
        printf("%d\n", solve(M / 2));
    }
    return 0;
}