\(O(n^2v)\)算法
用\(f(i,j)\)表示以位置i结尾，公差为j的等差数列有多少个。
转移的时候，枚举一个小于i的k，满足\(h_k+j= h_i\)
由f(k,j)转移到\(f(i,j)\)
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
26
27
| #include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
int a[N],f[N][40005];
const int ofs=20001,mod=998244353;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int ans=0;
for(int i=2;i<=n;++i){
for(int j=-20001;j<=20001;++j){
for(int k=1;k<i;++k){
if(a[k]+j==a[i]){
f[i][j+ofs]=(f[i][j+ofs]+f[k][j+ofs]+1)%mod;
}
}
ans=(ans+f[i][j+ofs])%mod;
}
}
printf("%d",(ans+n)%mod);
return 0;
}
|
\(O(nv)\)
注意到前两重循环交换后不影响结果正确性。我们此时先枚举公差j。
考虑之前\(O(n^2v)\)的算法转移的时候枚举一个小于i的k，然后当\(h_k = h_i- j\)的时候从\(f(k,j)\)转移到\(f(i,j)\)。
我们发现，转移相当于一个求和，对小于i的所有高度等于\(h_i-j\)的位置的\(f\)值求和。
令\(g(t)\)为\(\sum\limits_{1\leq k<i,h_k-j=t}f(k,j)\)
其含义为\(h_1\)到\(h_{i-1}\)，有多少高度为t结尾的等差数列。
在转移时，\(f(i)=g(h_i-j)\),同时维护g的值，\(g(h_i)+=f(i)\)
每次状态转移由\(O(n)\)优化到\(O(1)\)
对之前的代码稍作修改可通过该题,\(O(nv)\)，如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
int a[N],f[N][100005],g[100005];
const int ofs=40001,mod=998244353;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int ans=0;
for(int j=-20001;j<=20001;++j){
memset(g,0,sizeof g);
for(int i=1;i<=n;++i){
f[i][j+ofs]=(f[i][j+ofs]+g[a[i]-j+ofs])%mod;
g[a[i]+ofs]=(g[a[i]+ofs]+f[i][j+ofs]+1)%mod;
ans=(ans+f[i][j+ofs])%mod;
}
}
printf("%d",(ans+n)%mod);
return 0;
}
|
简单优化冗余
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>
using namespace std;
const int N=1000+5;
int a[N],f[N],g[80005];
const int ofs=40001,mod=998244353;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int ans=0;
for(int j=-20001;j<=20001;++j){
memset(g,0,sizeof g);
memset(f,0,sizeof f);
for(int i=1;i<=n;++i){
f[i]=g[a[i]-j+ofs]%mod;
g[a[i]+ofs]=(g[a[i]+ofs]+f[i]+1)%mod;
ans=(ans+f[i])%mod;
}
}
printf("%d",(ans+n)%mod);
return 0;
}
|
真·正解 \(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
| #include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
int a[N],f[N][80005];
const int ofs=40001,mod=998244353;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int ans=0;
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j){
int d=a[j]-a[i];
f[i][d+ofs]+=f[j][d+ofs]+1;
f[i][d+ofs]%=mod;
ans=(ans+f[j][d+ofs]+1)%mod;
}
}
printf("%d",(ans+n)%mod);
return 0;
}
|