明天就是入学考试了。。
虽然寒假一点学科都没搞，但是一点都不想复习呢。。
明天要跪烂了。。不管了
刷刷水题
一个简单的区间动规，从目标队形往回推，dp[l][r][k]表示[l,r]中最后一个人从第k边加入的方案数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// <chorus.cpp> - 02/27/16 04:07:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int mod=19650827; const int MAXN=1001; int dp[MAXN][MAXN][2]; int h[MAXN]; int main(){ freopen("chorus.in","r",stdin); freopen("chorus.out","w",stdout); int n=getint(); for(int i=1;i<=n;i++)h[i]=getint(),dp[i][i][0]=1; for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++){ if(h[i]<h[i+1])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][0])%mod; if(h[i]<h[j])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][1])%mod; if(h[j]>h[j-1])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%mod; if(h[j]>h[i])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%mod; } printf("%d",(dp[1][n][0]+dp[1][n][1])%mod); return 0; } |