ICPC上海网络赛J.Stone game

发表于 | 阅读数

题意：

分2堆石头，使得第一堆的总重量大于第二堆，并且去掉第一堆的任意一块，必有第一堆的重量小于等于第二堆，求分配方法的总数;

化简题意可得

简单的计数，为了能每次找到最小的$a[i]$将$A_{n}$从大到小排序，计数统计即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 3e2 + 10;
const int mod = 1e9 + 7;
const int M = 5e2 + 10;
int f[N * M];
int n, T, sum, a[N];
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int ans = 0;
        int sum = 0;
        memset(f, 0, sizeof(f));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), sum += a[i];
        f[0] = 1;
        sort(1 + a, 1 + a + n);
        for (int i = n; i >= 1; i--)
        {
            for (int j = sum; j >= a[i]; j--)
            {
                f[j] = (f[j - a[i]] + f[j]) % mod;
                if (sum <= j * 2 && j * 2 <= sum + a[i])
                    ans = (ans + f[j - a[i]]) % mod;
            }
            //cout << ans << endl;
        }

        printf("%d\n", ans);
    }
}