问题解决了,AC代码如下(我还以为会TLE得惨惨的呢):
```cpp
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int n,h[1010],dp[1010][20010][2],ans,w=1e9,v;
vector<int> c[20010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
v=max(v,h[i]);
w=min(w,h[i]);
c[h[i]].push_back(i);
}
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
for(int z=0;z<=1;z++){
dp[i][j][z]=1;
int t=h[i]+j*(z?1:-1);
if(t<w||t>v) continue;
for(int k=0;k<c[t].size()&&c[t][k]<i;k++) dp[i][j][z]=(dp[i][j][z]+dp[c[t][k]][j][z])%mod;
if(j>0||z) ans=(ans+dp[i][j][z]-1)%mod;
}
}
ans++;
}
printf("%d",ans);
return 0;
}
```
by YuRuochen @ 2022-10-06 20:44:00