bzoj 1996: [Hnoi2010]chorus 合唱隊

Description

為了在即將到來的晚會上有吏好的演出效果，作為AAA合唱隊負責人的小A需要將合唱隊的人根據他們的身高排出一個隊形。假定合唱隊一共N個人，第i個人的身髙為Hi米(1000<=Hi<=2000),并已知任何兩個人的身高都不同。假定最終排出的隊形是A 個人站成一排，為了簡化問題，小A想出了如下排隊的方式：他讓所有的人先按任意順序站成一個初始隊形，然后從左到右按以下原則依次將每個人插入最終棑出的隊形中：
-第一個人直接插入空的當前隊形中。
-對從第二個人開始的每個人，如果他比前面那個人髙(H較大)，那么將他插入當前隊形的最石邊。如果他比前面那個人矮(H較小)，那么將他插入當前隊形的最左邊。
當N個人全部插入當前隊形后便獲得最終排出的隊形。
例如，有6個人站成一個初始隊形，身卨依次為1850、1900、1700、1650、1800和1750,
那么小A會按以下步驟獲得最終排出的隊形：
1850

• 1850 , 1900 因為 1900 > 1850
• 1700, 1850, 1900 因為 1700 < 1900
• 1650 . 1700, 1850, 1900 因為 1650 < 1700
• 1650 , 1700, 1850, 1900, 1800 因為 1800 > 1650
• 1750， 1650, 1700，1850, 1900, 1800 因為 1750 < 1800
  因此，最終排出的隊形是 1750，1650，1700，1850, 1900，1800 小A心中有一個理想隊形，他想知道多少種初始隊形可以獲得理想的隊形

solution

正解：DP
簡單題啊，賦初值很坑，花了有點久
因為最終隊形的產生一定是左右逐漸擴展的，所以考慮區間DP.
最后一個加入的不是區間的左端點就是右端點，我們加入狀態考慮即可
設 \(dp[i][j][0/1]\)，表示區間 \([i,j]\)，已經形成理想隊列，最后一個加入的為左/右端點的方案數
注意賦初值時一定要直接給長度為2的區間賦值

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
using namespace std;
const int N=1005,mod=19650827;
int n,a[N],dp[N][N][2];
inline void add(RG int &x,int y){x+=y;if(x>=mod)x-=mod;}
void work()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<n;i++){dp[i][i+1][0]=a[i]<a[i+1];dp[i][i+1][1]=a[i]<a[i+1];}for(int k=2;k<n;k++){for(int i=1;i+k-1<=n;i++){RG int j=i+k-1;if(i>1){if(a[i-1]<a[i])add(dp[i-1][j][0],dp[i][j][0]);if(a[i-1]<a[j])add(dp[i-1][j][0],dp[i][j][1]);}if(j<n){if(a[j+1]>a[j])add(dp[i][j+1][1],dp[i][j][1]);if(a[j+1]>a[i])add(dp[i][j+1][1],dp[i][j][0]);}}}printf("%d\n",(dp[1][n][0]+dp[1][n][1])%mod);
}int main(){work();return 0;
}