P3205 [HNOI2010] 合唱队——区间dp

li_cat · 2025-04-27 17:59:47 · 个人记录

这是一个求方案数的区间问题

考虑使用 dp ，记 dp_{l,r,0} 为排出 [l,r] ，左/右端点为最后一个被放入的方案数

对于一个更大的区间，都有4种情况

• 对于左端点而言，可以是小区间的右端点先放入，再放入左端点；也可以是小区间的左端点先放入，再放入左端点
• 右端点同理

关于初始状态：见代码

AC Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MAXN=1e3+5;
const ll MOD=19650827;

ll dp[MAXN][MAXN][2];//[l,r]区间内排好的方案数，分别以l,r为最后一个放置 
ll h[MAXN];

ll r;

ll n;

void work(){
    //input...
    scanf("%lld",&n);
    for(ll i=1;i<=n;++i){
        scanf("%lld",&h[i]);
    }

    for(ll i=1;i<=n;++i)
        dp[i][i][0]=1;
//为什么设每一个初始点都只能从左边进来是对的？ 
//因为会发生重复的原因实际上是在枚举长度为2的区间进行转移时
//l+1=r,r-1=l,所以会被算两次，因为这两个是无论怎样都会被放在一起重叠的，所以无所谓是左来还是右来 

    for(ll len=2;len<=n;++len){
        for(ll l=1;l+len-1<=n;++l){
            r=l+len-1;
            if(h[l]<h[l+1]) dp[l][r][0]=(dp[l][r][0]+dp[l+1][r][0])%MOD;
            if(h[l]<h[r])   dp[l][r][0]=(dp[l][r][0]+dp[l+1][r][1])%MOD;
            if(h[r]>h[r-1]) dp[l][r][1]=(dp[l][r][1]+dp[l][r-1][1])%MOD;
            if(h[r]>h[l])   dp[l][r][1]=(dp[l][r][1]+dp[l][r-1][0])%MOD;
        }
    }

    printf("%lld",(dp[1][n][0]+dp[1][n][1])%MOD);
}

int main(){
    work();
    return 0;
}