题目描述

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 <bits/stdc++.h>

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;

}

巴特西

【洛谷P4933 大师】动态规划

题目描述

分析

AC代码

最新文章

热门文章