题解：P14360 [CSP-J 2025] 多边形 / polygon（民间数据）
yedalong
·
·
题解
背包 dp，应该有绿。
本题解将带领大家走一遍我考场上的思路。
以下的 a 数组是题目中的 l 数组。
Solution
很容易想到是 dp，开始猜状态。
但是这样有什么问题？我们不能保证这个加和的组成里没有大于 $a_i$ 的数，怎么办呢？考虑将数组排序一下，这样子会方便许多。
我们接着考虑状态，在这种情况下，设所有数字的加和为 $sum$，很容易想到答案为
$$
\sum_{i=1}^n{\sum_{j=a_i\times 2+1}^{sum}{dp_{i,j,1}}}
$$
为什么这样计算的答案不重不漏呢？因为这样是考虑以每一个 $a_i$ 为最大值的方案数。
至于转移，其实就是背包 dp 的模版。
$$
dp_{i,j,1}=dp_{i-1,j-a_i,1}+dp_{i-1,j-a_i,0}
$$
这是 $75$ 分的思路。
考虑优化。
我们发现会超时的原因是 $sum$ 太大了，我们思考一下，有必要一直转移到 $sum$ 吗，其实只要大于等于最大值 $maxn$ 的两倍加一也就是 $maxn\times2+1$ 就一定会产生贡献，因此枚举到 $maxn\times 2+1$ 就可以了。
但还是 $75$ 分，内存超限了。
直接滚动数组滚掉就好了。
时间复杂度 $O(n\times \max_{i=1}^na_i)$，可以通过此题。
## AC code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,a[5005],dp[2][10005][2],ans,maxx;
signed main(){
cin>>n;
for(int i = 1;i<=n;i++) cin>>a[i],maxx=max(maxx,a[i]);
dp[0][0][0]=1;
sort(a+1,a+1+n);
for(int i = 1;i<=n;i++){
for(int j = 0;j<=maxx*2+1;j++)
dp[i&1][j][0]=(dp[i&1^1][j][0]+dp[i&1^1][j][1])%mod,
dp[i&1][j][1]=0;
for(int j = maxx*2+1;j>=a[i];j--)
(dp[i&1][j][1]+=dp[i&1^1][j-a[i]][0]+dp[i&1^1][j-a[i]][1])%=mod;
for(int j = maxx*2+2-a[i];j<=maxx*2+1;j++)
(dp[i&1][maxx*2+1][1]+=dp[i&1^1][j][0]+dp[i&1^1][j][1])%=mod;
for(int j = a[i]*2+1;j<=maxx*2+1;j++)
(ans+=dp[i&1][j][1])%=mod;
}
cout<<ans;
return 0;
}
```