polygon 题解

a_foolish_OIer · 2025-11-01 12:52:12 · 题解

有史以来最简单的 T4。

直接 dfs 可以拿下 40。

考虑将 \max 拆掉，可以先对 a 进行排序，那么前 i 项的最大值为 a_i，对于 \sum，可以使用背包求解。

至于边数 \ge 3 这个限制，再加一维度表示选了 k 个木棍即可，k 只需要枚举到 3，所以记 f_{i,j,k} 表示前 i 项和为 j 选了 k 根木棍即可。

直接这么做是 O(n^2V) 的，考虑优化。

注意到 2 倍的 \max 是不会超过 10^4，所以对于 \sum 那一维，只需要枚举到 10^4，时间复杂度 O(nV)，大约带 8 倍常数。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'

const int N = 5e3 + 10;
const int M = 1e4 + 10;
const int mod = 998244353; 

int n,v;
int a[N];
int dp[2][M][5];

void add (int &x,int y){
    x += y;
    if (x >= mod) x -= mod;
}
void solve(){
    cin >> n; v = 0;
    for (int i = 1 ; i <= n ; i++) cin >> a[i],v = max(v,a[i]);
    sort(a + 1,a + n + 1);
    v = v * 2 + 1;
    dp[0][0][0] = 1;
    int cur = 0,ans = 0;
    for (int i = 0 ; i < n ; i++){
        int nxt = (cur ^ 1);
        for (int j = 0 ; j <= v ; j++){
            for (int k = 0 ; k <= 3 ; k++){
                if (!dp[cur][j][k]) continue;
                int jj = min(v,j + a[i + 1]),kk = min(k + 1,3ll);
                add(dp[nxt][jj][kk],dp[cur][j][k]);
                if (jj > 2 * a[i + 1] && kk == 3) add(ans,dp[cur][j][k]);
                add(dp[nxt][j][k],dp[cur][j][k]);
                dp[cur][j][k] = 0;
            } 
        }
        cur ^= 1; 
    }
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; //cin >> T;
    while (T--) solve();
    return 0; 
}