题解 P4622 【[COCI2012-2013#6] JEDAN】
浅色调
·
·
题解
Solution：
本题DP。
首先由题意不难确定一些性质：
1、合法情况首尾一定为0
2、最高高度小于n/2
3、由2可以确定的是第i位高度：当i\leq n/2，h_i最高为i-1; 当i>n/2，h_i最高为n-i
4、由于每次选择的是一段长度大于2的相等且连续的序列，而操作使(l,r)+1，所以相邻两位之差\in[-1,1]
然后就好做了。
考虑普通dp，定义状态f[i][j]表示第i位高度为j的方案数，那么由性质1确定初状态f[1][0]=1，目标状态为f[n][0]。
由性质4的邻位高度差绝对值\leq 1，不难得到状态转移方程：f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1]
转移时对于高度确定的就单次转移，否则就枚举可行高度并转移。
这样定义状态会炸空间，但是每次转移只与前一个数的状态有关，所以直接滚掉就好了。
### 代码：
```cpp
/*Code by 520 -- 9.4*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int mod=1e9+7;
int n,a[10005],f[2][10005],cnt,siz;
int main(){
scanf("%d",&n);
For(i,1,n) scanf("%d",&a[i]);
if(a[1]>0||a[n]>0) cout<<0,exit(0);
a[1]=a[n]=0,f[1][0]=1,siz=2;
while(siz<=n){
int up=siz;
if(siz>n/2) up=n-siz+1;
For(i,0,up-1) if(a[siz]==-1||i==a[siz])
f[cnt][i]=((ll)(i?f[!cnt][i-1]:0)+f[!cnt][i]+f[!cnt][i+1])%mod;
cnt^=1,++siz;
memset(f[cnt],0,sizeof(f[cnt]));
}
cout<<f[!cnt][0];
return 0;
}
```