首页技术正文

「HNOI2010」合唱队

程序员兰兰技术 2022年11月14日

0 收藏 573 点赞 3,964 浏览 907 个字

题目链接

戳我

$Solution$

令:

$f[i][j]$为$[i,j]$中最后排进去的是第i人

$dp[i][j]$为$[i,j]$中最后排进去的是第j人

则排头的元素即$f[i][j]$有两种插入方式：

$a[i]<=a[i+1]$
$a[i]<a[j]$

因为你在插入的时候可以放在队列两边

所以尾部的元素即$dp[i][j]$也有两种插入方式

$a[j-1]<a[j]$
$a[i]<a[j]$

所以直接枚举$j$转移就好了,复杂度为$O(n^2)$

Code

#include<bits/stdc++.h>
#define rg register
#define int long long
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
const int mod=19650827;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
int f[1001][1001],dp[1001][1001],a[1001];
main(){
    int n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        f[i][i]=1;
    for(int i=n;i>=1;i--)
        for(int j=i+1;j<=n;j++){
            if(a[i+1]>a[i])
                f[i][j]+=f[i+1][j];
            if(a[j]>a[j-1])
                dp[i][j]+=dp[i][j-1];
            if(a[i]<a[j])
                f[i][j]+=dp[i+1][j],dp[i][j]+=f[i][j-1];
            f[i][j]%=mod,dp[i][j]%=mod;
        }
    printf("%lld",(f[1][n]+dp[1][n])%mod);
}