题解：P12374 「LAOI-12」Sigma

· · 题解

题解里区间 dp 的题解好少啊，给一个区间 dp 的思路。

思路

用 dp_{i,j} 表示区间 [i,j] 的贡献，ndp_{i,j} 表示区间 [i,j] 的运算次数。定义 \text{query}(i,j) 为 i 到 j 的和。

根据题意，对于所有的 i(1 \le i \le n)，dp_{i,i}=\text{query}(1,a_i)，ndp_{i,i}=a_i。

枚举每一个区间 [i,j] 且 i<j。 观察到每个区间 [i,j] 都能由 [i,j-1] 转移过来（因为 [i,j] 对于 [i,j-1] 只多加了一个数）。

简单来说，如果区间 [i,j-1] 的贡献为：

\sum_{i_1=1}^{a_i} \sum_{i_2=2}^{a_{i+1}} ... \sum_{i_{j-i}=j-i}^{a_{j-1}} i_1+i_2...i_{j-i}

那么加入第 j 个数之后，就变成了：

\sum_{i_1=1}^{a_i} \sum_{i_2=2}^{a_{i+1}} ... \sum_{i_{j-i}=j-i}^{a_{j-1}} \sum_{i_{j-i+1}=j-i+1}^{a_{j}} i_1+i_2...i_{j-i}+i_{j-i+1}

显然最后一个区间长度为 a_j-(j-i+1)+1，一共算了 ndp_{i,j-1} 次。

所以转移就很好写了，先转移 ndp_{i,j}：

ndp_{i,j}=ndp_{i,j-1}\times (a_j-(j-i+1)+1)

再转移 dp_{i,j}：

dp_{i,j}=dp_{i,j-1} \times (a_j-(j-i+1)+1)+ndp_{i,j-1} \times \text{query}(j-i+1,a_j)

最后枚举每个 (1 \le i \le j \le n) 区间 [i,j]，求所有 dp_{i,j} 的和即可。即求：

\sum_{i=1}^n \sum_{j=i}^n dp_{i,j}

记得开 long long 和取模。

代码

#include<bits/stdc++.h>
using namespace std;
const int M=998244353;
long long n,a[5010],dp[5010][5010],ndp[5010][5010],sum;
long long query(long long x,long long y){
    return (x+y)*(y-x+1)/2%M;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i][i]=query(1,a[i]);
        ndp[i][i]=a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(j-i+1>a[j]) continue;
            ndp[i][j]=(ndp[i][j-1]*(a[j]-(j-i+1)+1)%M)%M;
            dp[i][j]=(dp[i][j-1]*(a[j]-(j-i+1)+1)%M+ndp[i][j-1]*query(j-i+1,a[j])%M)%M;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            sum=(sum+dp[i][j])%M;
        }
    }
    cout<<sum;
    return 0;
}