2025 多边形 · 方案二排序加计数 DP

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1998 字

枚举最长边，总和封顶后做计数背包

2025
动态规划

正文

// CSP-J 2025 复赛 T4 · 多边形（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSP2025JD
//
// 方案二 · 排序 + 按「总和」计数 DP
// 关键一：先把木棍按长度排序。规定每个合法选法只在「它里面下标最大的那根」处被统计一次，
//   于是枚举这根最靠后的木棍 a[i]，其余的只能从它前面那 i-1 根里挑。
//   这样一来 a[i] 天然就是选法里的最长边，条件变成「前面挑出的总和 > a[i]」且至少挑 2 根。
// 关键二：a[i] 最大只有 5000，所以总和只要超过 5000 就一定能满足条件，
//   再大的和没必要区分 —— 把总和「封顶」在 5001 就行，DP 数组一下就小了。
// 于是维护两个数组：
//   dp1[s] = 只从前面挑、恰好挑 1 根、总和为 s 的选法数；
//   dp2[s] = 只从前面挑、挑了 2 根或更多、总和为 s 的选法数。
// 每处理一根新木棍 x：先查 dp2 里总和 > x 的部分（后缀和）加进答案，
// 再把 x 并进 DP（分「不选 x」和「选 x」两部分，用一份拷贝避免重复统计）。
// 复杂度 O(n * 5001)，n = 5000 时约 2.5e7，稳过。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int CAP = 5001;          // 总和封顶：a[i] <= 5000，超过 5000 就一定满足条件

long long dp1[CAP + 1], dp2[CAP + 1];
long long ndp1[CAP + 1], ndp2[CAP + 1];
long long suf[CAP + 2];

int main() {
    freopen("polygon.in", "r", stdin);
    freopen("polygon.out", "w", stdout);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i];

        // 后缀和：suf[s] = dp2[s] + dp2[s+1] + ... + dp2[CAP]
        suf[CAP + 1] = 0;
        for (int s = CAP; s >= 0; s--) suf[s] = (suf[s + 1] + dp2[s]) % MOD;
        ans = (ans + suf[x + 1]) % MOD;      // 挑至少 2 根且总和 > x

        // 把 x 并进 DP：先拷一份表示「不选 x」
        for (int s = 0; s <= CAP; s++) {
            ndp1[s] = dp1[s];
            ndp2[s] = dp2[s];
        }
        int ns1 = x > CAP ? CAP : x;
        ndp1[ns1] = (ndp1[ns1] + 1) % MOD;   // 只选 x 这一根
        for (int s = 0; s <= CAP; s++) {
            int ns = s + x;
            if (ns > CAP) ns = CAP;
            ndp2[ns] = (ndp2[ns] + dp1[s] + dp2[s]) % MOD;   // 原来挑 1 根或更多，再选上 x
        }
        for (int s = 0; s <= CAP; s++) {
            dp1[s] = ndp1[s];
            dp2[s] = ndp2[s];
        }
    }
    cout << ans << "\n";
    return 0;
}

2025 多边形 · 方案二 排序加计数 DP

正文

CSP-J 标程 · 复赛真题的其它内容

2025 多边形 · 方案二排序加计数 DP