题目链接（洛谷）
题目大意
给出一个由$n$个正整数($\le 2e4$)组成的数列$h$。求有多少种方案，使得删除一些数后，剩下的数从左向右构成等差数列。
$n\le 1e3$，答案模$998244353$
分析
设$dp(i,j)$表示以$i$结尾公差为$j$的等差数列个数
转移：
枚举$k$，满足$h_k=h_i-j$，然后$dp(i,j)+=dp(k,j)+1$
时间复杂度：$O(n^2 k)$
优化：枚举第$i$个数前面那个数，得到公差进行转移
$dp(i,a_i-a_j)+=dp(j,a_i-a_j)+1$
时间复杂度：$O(n^2)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #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;
}
|