Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

Solution

辣雞guide真難用
Dev賽高！
一道蠻水的區間DP
很容易發現，當前要放進來的人只和已經排出的隊伍的兩端的大小關系有關
就很容易設計狀態表示f[x][y][0/1]表示當前已經排好[x,y]，且這次放的人在最左/最右邊
答案即為f[1][n][0]+f[1][n][1]
初始化狀態要設f[i][i][0]=1
答案記得取模

Code

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define N (1000+10) 5 using namespace std; 6 int n,a[N],f[N][N][2]; 7 int main() 8 { 9 scanf("%d",&n); 10 for (int i=1; i<=n; ++i) 11 scanf("%d",&a[i]); 12 for (int i=1; i<=n; ++i) 13 f[i][i][0]=1; 14 for (int i=2; i<=n; ++i) 15 for (int j=1; j<=n; ++j) 16 { 17 int x=j,y=x+i-1; 18 f[x][y][0]+=f[x+1][y][0]*(a[x]<a[x+1]); 19 f[x][y][0]+=f[x+1][y][1]*(a[x]<a[y]); 20 f[x][y][1]+=f[x][y-1][0]*(a[y]>a[x]); 21 f[x][y][1]+=f[x][y-1][1]*(a[y]>a[y-1]); 22 f[x][y][0]%=19650827; 23 f[x][y][1]%=19650827; 24 } 25 printf("%d",(f[1][n][0]+f[1][n][1])%19650827); 26 }

轉載于:https://www.cnblogs.com/refun/p/8880047.html

總結

以上是生活随笔為你收集整理的BZOJ1996:[HNOI2010]CHORUS 合唱队(区间DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。