题解：P14360 [CSP-J 2025] 多边形 / polygon

· · 题解

前言

高三老年人险些速通，但是被 P6686 混凝土数学中的思路带跑了一小时。
整体思路是通过枚举最大值来消掉式子中的 \max，比较经典的 trick。

思路

由于两种方案不同当且仅当选择的小木棍的下标集合不同，也就是我们不关心选出来的木棍怎么排序，那么这个多边形我们能知道的重要信息只有使用的木棍数量和使用的木棍长度最大值。

显然，这两个信息同时处理并不方便，我们肯定得先解决掉其中一个点。样例解释中解释是按照使用的木棍数量顺序给出的，考虑到一般黑心出题人都喜欢用样例解释误导选手，所以我考场上果断选择从使用的木棍长度最大值入手。

假设已知多边形最长的木棍是哪根，那么有多少种选法？
显然，选法数量就是用短于最长木棍的所有木棍拼出来的长度中，大于最长木棍长度的数量。

题目加粗文字中有“集合”二字，想一想可以发现：从集合中挑出一些数，求组成某个和的方案有多少种，这是经典的 01 背包计数问题。

于是我们可以升序枚举用到的最长木棍，并求出所对的方案数。

特别地，对于大于 \max a_i 的长度的方案数，我们并不关心他们实际有多长，全部记为长度为 5001 即可。

时间复杂度为 O(n\times\max a_i)。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,a[5005],f[5005]={1},ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        for(int j=5001;j>a[i];j--)(ans+=f[j])%=mod;
        for(int j=5001;j>=5001-a[i];j--)(f[5001]+=f[j])%=mod;
        for(int j=5000;j>=a[i];j--)(f[j]+=f[j-a[i]])%=mod;
    }
    cout<<ans;
    return 0;
}