BZOJ1996: [Hnoi2010]chorus 合唱队【区间DP】

1996: [Hnoi2010]chorus 合唱队

【题目描述】

传送门

【题解】

区间DP,f[i][j][0/1]表示这个放了i~j区间最后一次放在前0后1的方案数。
比较当前放入的点于之前放入的点就可以了。

代码如下

#include<cstdio>
using namespace std;
const int MOD=19650827;
int n,a[1005],f[1005][1005][2];
void MO(int &x){if(x>=MOD) x-=MOD;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i][i][0]=f[i][i][1]=1;
    for(int L=2;L<=n;L++)
    for(int i=1;i+L-1<=n;i++){
        int j=i+L-1;
        if(a[i]<a[i+1]) MO(f[i][j][0]+=f[i+1][j][0]);
        if(a[i]<a[j]&&L>2) MO(f[i][j][0]+=f[i+1][j][1]);
        if(a[j-1]<a[j]) MO(f[i][j][1]+=f[i][j-1][1]);
        if(a[i]<a[j]&&L>2) MO(f[i][j][1]+=f[i][j-1][0]);
    }
    printf("%d\n",(f[1][n][0]+f[1][n][1])%MOD);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部