P4933 大师(dp)

题目背景

建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。

题目描述

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

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

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

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

同时也要注意，等差数列的公差也可以为负数。

输入格式

第一行一个正整数 n。

第二行 n 个非负整数，第 i 个整数是第 ii 个电塔的高度 h[i] 。

输出格式

输出一个整数，表示美观的方案数模 998244353的值。

输入输出样例

输入

8

13 14 6 20 27 34 34 41 

输出

50

数据说明

n<=1e3,v<=2e5

思路

考虑dp，f[i][j]代表到i位置公差为j的等差数列个数，则有f[i][a[i]-a[j]]+=f[j][a[i]-a[j]]+1,j<i;

这里的加一是考虑每次只有a[i]和a[j]两个数的数列，数组初始化默认为0，则最后ans需要加上n,

即每个数单独成为一个等差数列，这里的公差可能小于0，为防止越界则在数组第二维都加上maxn。

算法复杂度o(n^2)

#include<bits/stdc++.h>
using namespace std;
const int maxn=20005;
const int mod=998244353;
int a[1005];
long long int f[1005][2*maxn];
long long int ans;
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            f[i][a[i]-a[j]+maxn]+=f[j][a[i]-a[j]+maxn]+1;
            f[i][a[i]-a[j]+maxn]%=mod;
            ans=(ans+f[j][a[i]-a[j]+maxn]+1)%mod;
        }
    }
    ans=(ans+n)%mod;
    cout<<ans<<endl;
    return 0;
}