http://www.lydsy.com/JudgeOnline/problem.php?id=1996
f[i][j][0] 表示已经排出队形中的 [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 都行
1996: [Hnoi2010]chorus 合唱队
#include<cstdio>
#include<iostream>
using namespace std;
#define N 1001
const int mod=19650827;
int a[N];
int f[N][N][2];
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
int main()
{
int n;
read(n);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i) f[i][i][1]=1;
int j;
for(int len=2;len<=n;++len)
for(int i=1;i+len-1<=n;++i)
{
j=i+len-1;
if(a[i]<a[i+1]) f[i][j][0]+=f[i+1][j][0];
if(a[i]<a[j]) f[i][j][0]+=f[i+1][j][1];
if(a[j]>a[i]) f[i][j][1]+=f[i][j-1][0];
if(a[j]>a[j-1]) f[i][j][1]+=f[i][j-1][1];
while(f[i][j][0]>=mod) f[i][j][0]-=mod;
while(f[i][j][1]>=mod) f[i][j][1]-=mod;
}
int ans=f[1][n][0]+f[1][n][1];
if(ans>=mod) ans-=mod;
cout<<ans;
}
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
来源: http://www.bubuko.com/infodetail-2456934.html