bzoj千题计划211：bzoj1996: [Hnoi2010]chorus 合唱队

http://www.lydsy.com/JudgeOnline/problem.php?id=1996

f[i][j][0/1] 表示已经排出队形中的[i,j]，最后一个插入的人在[i,j]的i或j

枚举顺序一：

先枚举区间长度，再枚举区间左端点

枚举顺序二：

先倒序枚举区间左端点，再枚举区间右端点

初始化：

当长度为2时，转移方程中的j==i+1，i==j-1

令f[i][j]只累加一次，所以f[i][i][0]=1 或者是 f[i][i][1]=1都行

#include<cstdio>

#include<iostream>

using namespace std;

#define N 1001

const int mod=;

int a[N];

int f[N][N][];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c))  c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();  }

}

int main()

{

    int n;

    read(n);

    for(int i=;i<=n;++i) read(a[i]);

    for(int i=;i<=n;++i) f[i][i][]=;

    int j;

    for(int len=;len<=n;++len)

        for(int i=;i+len-<=n;++i)

        {

            j=i+len-;

            if(a[i]<a[i+]) f[i][j][]+=f[i+][j][];

            if(a[i]<a[j]) f[i][j][]+=f[i+][j][];

            if(a[j]>a[i]) f[i][j][]+=f[i][j-][];

            if(a[j]>a[j-]) f[i][j][]+=f[i][j-][];

            while(f[i][j][]>=mod) f[i][j][]-=mod;

            while(f[i][j][]>=mod) f[i][j][]-=mod;

        }

    int ans=f[][n][]+f[][n][];

    if(ans>=mod) ans-=mod;

    cout<<ans;

}

1996: [Hnoi2010]chorus 合唱队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 1891  Solved: 1232
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT