P3205 [HNOI2010] 合唱队

· · 题解

P3205 [HNOI2010] 合唱队

题目翻译：

太简单了，就不翻译了

思路：

一道很不像区间dp的区间dp，我们知道，不管是理想队形，还是初始队形，其大小都为n，那我们令i,j表示已经加入的队形在最终队形的i到j中则令f[i][j][0]表示把点从左边加入第i人，而f[i][j][1]表示将第j人从右边加入。由此可以推出三种情况：

先令第i个人的高度为h[i]

$$$dp[i][j][0]+=dp[i+1][j][0] (h[i]<h[i+1])$$$ $2.$若上一个人是$j$那它上次就是从右边加入，而$h[i]<h[j]$，则它比上一个矮，那它就应该从左边加入，则： $$$dp[i][j][0]+=dp[i+1][j][1] (h[i]<h[j])$$$ $3.$若上一个人是$j-1$而我的高度$h[j]>h[j-1]$，那我比上一个高，就应该从右边加入，则： $$$dp[i][j][1]+=dp[i][j-1][1] (h[j-1]<h[j])$$$ $4.$若上一个人是$i$，且我的高度$h[j]>h[i]$则我还是因该从右边加入，则 $$$dp[i][j][1]+=dp[i][j-1][0] (h[j]>h[i])$$$ 为了保证$dp$时所有子区间已经$dp$，则我们根据长度$dp$即可 # 完整代码： 
#include<bits/stdc++.h>
using namespace std;
const int N=2000;
const int P=19650827;
int dp[N][N][2];
int h[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        dp[i][i][0]=1;
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            if(h[i]<h[i+1])dp[i][j][0]+=dp[i+1][j][0];
            if(h[i]<h[j])dp[i][j][0]+=dp[i+1][j][1];
            if(h[j]>h[i])dp[i][j][1]+=dp[i][j-1][0];
            if(h[j]>h[j-1])dp[i][j][1]+=dp[i][j-1][1];
            dp[i][j][0]%=P;
            dp[i][j][1]%=P;
        }
    }
    cout<<(dp[1][n][0]+dp[1][n][1])%P<<endl;
}

区间DP讲解