题解 P4933 【大师】

· · 题解

这题莫名其妙的，怎么算复杂度都是O(n^3)啊……求解释或hack

求给定序列中子序列为等差数列的个数。

记f[i][j]为倒数第二项为a[i],最后一项为a[j]的等差数列的总数；若i=0，说明这个等差数列只有1项。

这样可以二维转移。对于任意a[i],a[j](i<j)，若某一项a[k](k<i)能满足a[j]-a[i]=a[i]-a[k]，那么在所有以a[k],a[i]为结尾的等差数列肯定可以往后延伸一个a[j]。所以f[i][j]+=f[k][i]，转移方程基本成型。

初始化，每个数也可以单独成一个等差数列，那么f[0][i]=1(1\leq i\leq n)。

转移，f[i][j]=f[0][i]+ \Sigma_{k=1}^{i-1}[a[j]-a[i]=a[i]-a[k]]f[k][i])。每次枚举i,j,k，枚举到n即可。

最后统计所有的f[i][j]的和就是答案

然后复杂度不对但就是水过了（

附上AC代码

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

int n,ans;
int h[maxn];
int f[maxn][maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]),f[0][i]=1; ///在这里就初始化了
    ans+=n; ///统计答案
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            f[j][i]=f[0][j];
            for(int k=1;k<j;k++) if(h[j]*2==h[k]+h[i]) f[j][i]=(f[j][i]+f[k][j])%mod;
            ans=(ans+f[j][i])%mod;
        }
    printf("%d",ans);
    return 0;
}