洛谷 P3205 [HNOI2010]合唱队（区间dp）

传送门

解题思路

观察队形的组成方式可以得出，最后一名加入区间i...j的人要么是在i位置上，要么是在j位置上，所以我们可以用dp[i][j][0]表示区间i...j最后一个加入的人站在i位置上的方案总数，同理，用dp[i][j][1]表示区间i...j最后一个加入的人站在j位置上的方案总数。

然后分情况讨论即可。

最后答案等于dp[1][n][0]+dp[1][n][1]。

别忘了对所有的操作进行取余。

AC代码

 1 #include<iostream>
 2 using namespace std;
 3 int n,dp[1005][1005][2],a[1005];
 4 const int mod=19650827;
 5 int main()
 6 {
 7     cin>>n;
 8     for(int i=1;i<=n;i++){
 9         cin>>a[i];
10         dp[i][i][0]=dp[i][i][1]=1;
11     }
12     for(int i=1;i<=n;i++){
13         int j=i+1;
14         if(j>n) break;
15         if(a[i]<a[j]) dp[i][j][0]=dp[i][j][1]=1;
16     }
17     for(int len=3;len<=n;len++){
18         for(int i=1;i<=n;i++){
19             int j=i+len-1;
20             if(j>n) break;
21             if(a[i]<a[i+1]){
22                 dp[i][j][0]+=dp[i+1][j][0];
23             }
24             if(a[i]<a[j]){
25                 dp[i][j][0]+=dp[i+1][j][1];
26             }
27             if(a[j]>a[i]){
28                 dp[i][j][1]+=dp[i][j-1][0];
29             }
30             if(a[j]>a[j-1]){
31                 dp[i][j][1]+=dp[i][j-1][1];
32             }
33             dp[i][j][0]%=mod;
34             dp[i][j][1]%=mod;
35         }
36     }
37     cout<<(dp[1][n][0]+dp[1][n][1])%mod;
38     return 0;
39 }