题解：P14360 [CSP-J 2025] 多边形 / polygon（民间数据）

· · 题解

背景

考场应该切了，4 题总用时 30 分钟。

题意

给你 n 个木棍，求出可以拼出的多边形数？

分析

符合条件要满足 \sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i。

不妨两边都减去 \max_{i=1}^{m} l_i。

变成 \sum_{i=1}^{m} l_i -\max_{i=1}^{m} l_i> \max_{i=1}^{m} l_i。

这个是不是更加熟悉了。

注意到，排序就可以解决最大值的问题。

那么问题就变成了，对于每一个 i，求前面大于 a_i 的方案数。

明显背包版题，只是注意到 \sum_{i=1}^{n} a_i 很大，直接做会超时加超空间。

但我们只要求大于 a_i 的方案数，而且 a_i \le 5000，那么把 5001 到 \sum_{i=1}^{n} a_i 都放进 dp_{5001} 就行了。

Code

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) freopen(x".in","r",stdin)
const int N=5e3+5,M=1e5+10,mod=998244353;
int n;
int a[N];
int dp[M];
void work(){
    cin>>n;
    int V=0,ans=0;
    for(int i=1;i<=n;i++)
        cin>>a[i],V+=a[i];
    V=min(V,5001);
    sort(a+1,a+n+1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=V;j++)
            ans=(ans+dp[j])%mod;
        for(int j=V;j>=0;j--)
            dp[min(j+a[i],5001)]=(dp[min(j+a[i],5001)]+dp[j])%mod;
        //通过min(j+a[i],5001)实现把大于压缩进一个
    }
    cout<<ans;
}
void clear(){}
signed main(){
    int _=1;
    while(_--)work(),clear();
    return 0;
}
/*

*/

评价

T4 放板子题太水了，今年 CSP-S 我考炸了，也算是安慰吧！