做公众号关注网站/广州网络营销运营

分析

题目大意：有N个位置，一开始高度为0。每次可以选择一段具有相同距离的区间$[A..B]$，使得在$[A+1..B-1]$的区间内的所有高度+1。已知部分积木的高度，求满足这部分积木高度的摆法有多少种。

DP水法： 我们注意到“选定一个拥有相同高度的区间[A…B]，
然后将位置$[A+1..B-1]$上的所有积木的高度加一”显然可以得出相邻的积木高度只能为0或1，
那么设$f[i][j]$表示第i个积木，高度为j的方案数，
对于积木$i$高度为$j$显然是它相邻的积木的高度为$j+1$或$j-1$推过来的；
对于被推倒的积木只需要枚举j就行了。
所以方程为$$F[i][j]=f[i][j]+f[i-1][j-1]+f[i-1][j+1];$$
但是我们要判断这个方案的合法性比如说 0 0 0变成0 1 1是不合法的因为没有区间能转移成这个状态。

其实这个并不是题解给出的真正的正解，但是通过一些奇技淫巧（O3优化，register，别用cin）就可以通过。

上代码

#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
//玄学分界线--------------------- 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int mod=1000000007;
int n,a[20001];
long long f[2][10001];int hi(int x)
{if(x<n/2+1) return x-1;return n-x;
}int main()
{freopen("brick.in","r",stdin);freopen("brick.out","w",stdout);scanf("%d",&n);for(register int i=1;i<=n;i++){scanf("%d",&a[i]);}f[0][0]=1;for(register int i=1;i<=n;i++){int x=hi(i),y=hi(i-1);if(a[i]!=-1){if(a[i]<=x){f[1][a[i]]+=f[0][a[i]];if(a[i]>=1){f[1][a[i]]+=f[0][a[i]-1];}if(a[i]+1<=y){f[1][a[i]]+=f[0][a[i]+1];} f[1][a[i]]%=mod;}}else{for(register int j=0;j<=x;j++){f[1][j]+=f[0][j];if(j>=1){f[1][j]+=f[0][j-1];}if(j+1<=y){f[1][j]+=f[0][j+1];}f[1][j]%=mod;}}memcpy(f[0],f[1],sizeof(f[1]));memset(f[1],0,sizeof(f[1]));}printf("%d",f[0][0]%mod);return 0;}