P4622 [COCI2012-2013#6] JEDAN

题目背景

COCI

题目描述

有N个数排成一行(数值代表高度)，最初所有的数都为零，你可以选择连续的一段等高的数，将它们都增加1(除了开头和结尾那个数)如下图表示了两次操作:

现在有一些数字看不清了，我们用-1表示，请你根据留下的数字，推出有多少种可能的方案。使得留下的数字正好满足上面的操作方法。

输入输出格式

输入格式：

第一行一个正整数N表示数的个数。
接下来一行N个数，依次表示每一个数的大小，-1表示看不清楚，你可以用任
意满足条件的数代替。第i个数用hi表示

输出格式：

一个数，表示所有可能的方案对1000000007求余的值。

输入输出样例

输入样例#1：

3

-1 2 -1

输出样例#1：

输入样例#2：

3

-1 -1 -1

输出样例#2：

输入样例#3：

6

-1 -1 -1 2 -1 -1

输出样例#3：

说明

(1≤N≤10000)
(−1≤hi≤10000)

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

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

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

代码：

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

int n,a[],f[][],cnt,siz;

int main(){

    scanf("%d",&n);

    For(i,,n) scanf("%d",&a[i]);

    if(a[]>||a[n]>) cout<<,exit();

    a[]=a[n]=,f[][]=,siz=;

    while(siz<=n){

        int up=siz;

        if(siz>n/) up=n-siz+;

        For(i,,up-) if(a[siz]==-||i==a[siz])

            f[cnt][i]=((ll)(i?f[!cnt][i-]:)+f[!cnt][i]+f[!cnt][i+])%mod;

        cnt^=,++siz;

        memset(f[cnt],,sizeof(f[cnt]));

    }

    cout<<f[!cnt][];

    return ;

}

巴特西

P4622 [COCI2012-2013#6] JEDAN

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章