洛谷 P3205 [HNOI2010]合唱队

题目传送门

解题思路:

f[i][j][0]表示i~j区间最后一个进来的元素是i.

f[i][j][1]表示i~j区间最后一个进来的元素是j.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int n,a[1001],f[1001][1011][2];
 8 
 9 int main() {
10     scanf("%d",&n);
11     for(int i = 1;i <= n; i++)
12         scanf("%d",&a[i]);
13     for(int i = 1;i <= n; i++)
14         f[i][i][0] = 1;//只有一个元素时,默认从左边进来的 
15     for(int len = 1;len < n; len++) 
16         for(int i = 1,j = len + i;j <= n; i++,j++) {
17             if(a[i] < a[j]) f[i][j][0] += f[i+1][j][1];
18             if(a[i] < a[i+1]) f[i][j][0] += f[i+1][j][0];
19             if(a[j] > a[i]) f[i][j][1] += f[i][j-1][0];
20             if(a[j] > a[j-1]) f[i][j][1] += f[i][j-1][1];
21             f[i][j][1] %= 19650827;
22             f[i][j][0] %= 19650827;
23         }
24     printf("%d",(f[1][n][1] + f[1][n][0]) % 19650827);
25     return 0;
26 }