自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 22:02:03，当前版本为作者最后更新于2018-09-12 08:23:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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]$

转移时对于高度确定的就单次转移，否则就枚举可行高度并转移。

这样定义状态会炸空间，但是每次转移只与前一个数的状态有关，所以直接滚掉就好了。

$\quad\;\;$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处，万分感谢！～）

代码：

/*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;
}