题目描述

ljt12138首先建了n个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为1到n，第i个电塔的高度为h[i]。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模998244353。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

分析

题目的大致意思就是求当前数列的等差数列的个数

我们就定义状态是f[i][j]表示到第i个数，公差是j的等差数列的方案总数。

\[ F_{i\ j}=F_{i\ j}+F_{k\ j}+1\]

k是要枚举

AC代码

#include 
    
     using namespace std;const int Mod=998244353;int n,V;int H[1005],f[1005][40005];inline int read() {    int w=0,x=0; char ch=0;    while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}    while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}    return w?-x:x;}int Max(int n,int m) {return n>m?n:m;}int main() {    n=read();    for (int i=1;i<=n;i++) H[i]=read();    int ans=0;    for (int i=1;i<=n;i++) {        ans=(ans+i)%Mod;        for (int j=i-1;j;j--) {            int X=H[i]-H[j];            ans=(ans+f[j][X+10005])%Mod;            f[i][X+10005]=(f[i][X+10005]+f[j][X+10005]+1)%Mod;        }    }    printf("%d\n",ans);    return 0;}