AGC041D Problem Scores 题解

在分值不降的条件下，要使任意一个大小为 \(k\) 的子集 \(S\) 内题目的分值之和少于任意一个大小为 \(k + 1\) 的子集 \(T\) 内题目的分值之和，容易发现只需要取 \(S\) 为后 \(k\) 道题目，\(T\) 为前 \(k + 1\) 道题目时满足限制即可。

换而言之，只需要对满足 \(a\) 的每一段长为 \(k + 1\) 的前缀的和大于对应的长为 \(k\) 的后缀的和的方案计数。

为了方便，可以把分值不降的限制转化为：初始令所有 \(a_i = n\)，每次选择一个前缀并整体减一，但必须保证所有 \(a_i\) 为正整数。

朴素地，设 \(dp_{i, a, b}\) 表示已经处理完前缀 \(i\)，前缀和为 \(a\)，后缀和为 \(b\) 的方案数。

套路地，设差分变量：\(j = a - b\)，为了合法，令 \(j > 0\)。\(dp_{i, j}\) 表示已经处理完前缀 \(i\)，前缀和减后缀和为 \(j\) 的方案数。

容易描述每次选择前缀并整体减一后 \(j\) 的变化。问题就转化为一个完全背包问题：有 \(n\) 种物品，每种物品有无限个，物品的体积确定，问总体积小于 \(n\) 的条件下可以选择的最多的物品数量。

再套路地压缩第一维，跑完全背包即可。时间复杂度 \(O(n^2)\)。

参考代码如下。（需要指出代码中的背包是反过来跑的）

#include <iostream>

#define int long long

using namespace std;

int n, mod;
int w[5005];
int dp[5005];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("AGC041D.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> mod;
    for (int i = 1; i <= (n + 1) / 2; ++i)
        w[i] = i;
    for (int i = n; i > n / 2; --i)
        w[i] = n - i + 1;
    dp[n] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = n; j >= w[i]; --j)
            dp[j - w[i]] = (dp[j - w[i]] + dp[j]) % mod;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += dp[i];
    cout << ans % mod << endl;
    return 0;
}