题面
本题的重点是发现abs( a[ i ] - a[ i-1 ] ) <=1
所以我们分类讨论。相邻转移即可。
然后发现有两维，M掉了
由于只要用到两个相邻的位置，位置那一维滚掉就好了
1 #include<stdio.h>
2 #define int long long
3 #define For(i,a,b) for(register long long i=(a);i<=(b);i++)
4 using namespace std;
5 const int maxn=1e4+10,mod=1e9+7;
6 int n,dp[2][maxn],h[maxn];
7 inline void nxt(){
8 For(i,0,n){
9 dp[0][i]=dp[1][i],dp[1][i]=0;
10 }
11 }
12 signed main(){
13 scanf("%lld",&n);
14 For(i,1,n){
15 scanf("%lld",&h[i]);
16 }
17 if( (h[1]!=0&&h[1]!=-1) || (h[n]!=0&&h[n]!=-1) ){
18 printf("0
");
19 return 0;
20 }
21 dp[0][0]=1;
22 For(i,2,n){
23 if(h[i]!=-1){
24 if(h[i]==0){
25 dp[1][0]=(dp[0][1]+dp[0][0])%mod;
26 }else{
27 dp[1][h[i]]=(dp[0][h[i]]+dp[0][h[i]-1]+dp[0][h[i]+1])%mod;
28 }
29 nxt();
30 continue;
31 }
32 dp[1][0]=(dp[0][0]+dp[0][1])%mod;
33 For(j,1,n){
34 dp[1][j]=((dp[0][j-1]+dp[0][j])%mod+dp[0][j+1])%mod;
35 }
36 nxt();
37 }
38 printf("%lld
",(dp[0][0]%mod+mod)%mod);
39 }