洛谷 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代码

 #include<iostream>

 using namespace std;

 int n,dp[][][],a[];

 const int mod=;

 int main()

 {

     cin>>n;

     for(int i=;i<=n;i++){

         cin>>a[i];

         dp[i][i][]=dp[i][i][]=;

     }

     for(int i=;i<=n;i++){

         int j=i+;

         if(j>n) break;

         if(a[i]<a[j]) dp[i][j][]=dp[i][j][]=;

     }

     for(int len=;len<=n;len++){

         for(int i=;i<=n;i++){

             int j=i+len-;

             if(j>n) break;

             if(a[i]<a[i+]){

                 dp[i][j][]+=dp[i+][j][];

             }

             if(a[i]<a[j]){

                 dp[i][j][]+=dp[i+][j][];

             }

             if(a[j]>a[i]){

                 dp[i][j][]+=dp[i][j-][];

             }

             if(a[j]>a[j-]){

                 dp[i][j][]+=dp[i][j-][];

             }

             dp[i][j][]%=mod;

             dp[i][j][]%=mod;

         }

     }

     cout<<(dp[][n][]+dp[][n][])%mod;

     return ;

 }