M_sea

洛谷3205 [HNOI2010]合唱队
Luogu算法区间DP。设$f[i][j]$表示i到j区间,最后加入i的方案总数,$g[i][j]$表示i到j区间...
扫描右侧二维码阅读全文
30
2018/07

洛谷3205 [HNOI2010]合唱队

Luogu

算法

区间DP。

设$f[i][j]$表示i到j区间,最后加入i的方案总数,$g[i][j]$表示i到j区间,最后加入j的方案总数。

对于$f[i][j]$的转移:

  • 若$a[i]<a[i+1]$,有$f[i][j]+=f[i+1][j]$。
  • 若$a[i]<a[j]$,有$f[i][j]+=g[i+1][j]$。

对于$g[i][j]$的转移:

  • 若$a[j]>a[j-1]$,有$g[i][j]+=g[i][j-1]$。
  • 若$a[j]>a[i]$,有$g[i][j]+=f[i][j-1]$。

注意边界为$f[i][i]=0$,不需要置$g$,否则会WA(玄学边界)

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MOD=19650827;

int a[1010];
int f[1010][1010]; //f[i][j]表示i到j区间,最后加入i的方案总数 
int g[1010][1010]; //g[i][j]表示i到j区间,最后加入j的方案总数

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) a[i]=read(),f[i][i]=1;
    for (re int l=2;l<=n;l++)
        for (re int i=1;i+l-1<=n;i++) {
            int j=i+l-1;
            if (a[i]<a[i+1]) f[i][j]+=f[i+1][j];
            if (a[i]<a[j]) f[i][j]+=g[i+1][j];
            if (a[j]>a[j-1]) g[i][j]+=g[i][j-1];
            if (a[j]>a[i]) g[i][j]+=f[i][j-1];
            f[i][j]%=MOD,g[i][j]%=MOD;
        }
    printf("%d\n",(f[1][n]+g[1][n])%MOD);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 37 PM

发表评论