OI Problems   关于

Θ(n3)∼Θ(n4)\Theta(n^3)\sim\Theta(n^4) 动态规划

容易想到记 f(i,j,k)f(i,j,k) 表示 a[i−1]=ka[i-1]=k 且 a[i−2]=ja[i-2]=j 时的方案总数。

转移时间复杂度 Θ(n)\Theta(n)，总时间复杂度 Θ(n4)\Theta(n^4)。

前缀和优化后可以做到 Θ(n3)\Theta(n^3)。


正解做法

考虑减少状态数目。

记 f(i,j,0)f(i,j,0) 表示处理到 aia_i 满足 ai−1≤ai=ja_{i-1}\leq a_i=j，且右端点可能情况已计算时的方案数，f(i,j,1)f(i,j,1) 表示处理到 aia_i 满足 j=ai−1>aij=a_{i-1}>a_i，且右端点可能情况未计算时的方案数。

前缀和优化可以做到 Θ(n2)\Theta(n^2)。

  代码
// 2023.10.13

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;

int n,w[4001],sum[4001];
long long dp[4001][4001][2],f[4001],g[4001];
// dp[i][j][0] 表示处理到 a[i] 满足 a[i-1]<=a[i]=j，且右端点可能情况已计算
// dp[i][j][1] 表示处理到 a[i] 满足 j=a[i-1]>a[i]，且右端点可能情况未计算

int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",w+i),sum[i]=(sum[i-1]+w[i])%mod;
    for(int i=1;i<=n;i++){
        dp[3][i][0]=(1ll*i*w[i]%mod+sum[n]-sum[i])%mod*i%mod;
        dp[3][i][1]=(1ll*i*w[i]%mod+sum[n]-sum[i])%mod;
    }
    for(int i=4;i<=n;i++){
        for(int j=1;j<=n;j++)
            dp[i][j][1]=dp[i-1][j][0]*w[j]%mod;
        for(int j=1;j<=n;j++){
            f[j]=(f[j-1]+dp[i-1][j][0]+dp[i-1][j][1]*(j-1))%mod;
            g[j]=(g[j-1]+dp[i-1][j][1]*w[j])%mod;
        }
        for(int j=1;j<=n;j++){
            dp[i][j][0]=f[j]*w[j]%mod,
            dp[i][j][0]+=(g[n]-g[j])*j%mod;
            dp[i][j][1]+=g[n]-g[j];
        }
        for(int j=1;j<=n;j++)
            dp[i][j][0]%=mod,dp[i][j][1]%=mod;
    }
    long long answer=0;
    for(int i=1;i<=n;i++)
        answer+=dp[n][i][0]+dp[n][i][1]*(i-1)%mod;
    printf("%lld\n",answer%mod);
    return 0;
}