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

背包 dp，应该有绿。

本题解将带领大家走一遍我考场上的思路。

以下的

a

数组是题目中的

l

数组。

Solution

很容易想到是 dp，开始猜状态。

dp_{i,j,k}

表示到了第

i

个，加和为

j

，第

i

个选或不选的方案数，答案枚举得。

但是这样有什么问题？我们不能保证这个加和的组成里没有大于

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;
}

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

文章操作

Solution

AC code

相关推荐

评论

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