题目链接（洛谷）
题目大意
给出一个由\(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;
}
|