【题解】P4933 大师

发表于 2021-02-24 分类于信息学阅读次数： 16 Valine：

题目链接（洛谷）

题目大意

给出一个由 $n$ 个正整数( $\leq 2 e 4$ )组成的数列 $h$ 。求有多少种方案，使得删除一些数后，剩下的数从左向右构成等差数列。

$n \leq 1 e 3$ ，答案模 $998244353$

分析

设 $d p (i, j)$ 表示以 $i$ 结尾公差为 $j$ 的等差数列个数

转移：

枚举 $k$ ，满足 $h_{k} = h_{i} - j$ ，然后 $d p (i, j) + = d p (k, j) + 1$

时间复杂度： $O (n^{2} k)$

优化：枚举第 $i$ 个数前面那个数，得到公差进行转移

$d p (i, a_{i} - a_{j}) + = d p (j, a_{i} - a_{j}) + 1$

时间复杂度： $O (n^{2})$

代码

#include<bits/stdc++.h>
#define ll long long
const ll mod=998244353;
const int p=20004;
using namespace std;
ll ans;
int n,h[1003],dp[1003][40004];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        ans++;
        for(int j=1;j<i;j++){
            dp[i][h[i]-h[j]+p]+=dp[j][h[i]-h[j]+p]+1;
            dp[i][h[i]-h[j]+p]%=mod;
            ans+=dp[j][h[i]-h[j]+p]+1;
            ans%=mod;
        }
    }

    cout<<ans;
    return 0;
}