526互联

P3205 [HNOI2010] 合唱队

发布时间 2023-12-06 21:09:06作者: 纯粹的

原题链接

导入

1.对于一个给定的序列，最后一个加进来的元素不是最左端就是最右端，如果是最左端，那么代表去掉最左端的序列中最后一个加进来的元素比最左端小，最右端同理。
2.对于一个给定的序列，可能的排序结果无非两类，一类是以最左端的元素结尾的，一类是以最右端的元素结尾的。因此设\(sum[i][j][k],k\in \{0,1\}\)为序列\([i,j]\)的可能排列数，其中k=0时代表最后一个元素是最左端，k=1时代表最后一个元素是最右端。

提醒

一定要训练用直接dp的方法做而不是用递归！

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll sum[2002][2002][2]={0};
int main()
{
    ll n;
    scanf("%lld",&n);
    ll a[2005]={0};
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(ll i=1;i<=n-1;i++) if(a[i]<a[i+1])sum[i][i+1][0]=sum[i][i+1][1]=1;

    for(ll k=2;k<=n;k++)
        for(ll i=1;i+k<=n;i++)
        {
            if(a[i]<a[i+1])sum[i][i+k][0]=(sum[i][i+k][0]+sum[i+1][k+i][0])%19650827;
            if(a[i]<a[i+k])sum[i][i+k][0]=(sum[i][i+k][0]+sum[i+1][k+i][1])%19650827;
            if(a[i+k]>a[i])sum[i][i+k][1]=(sum[i][i+k][1]+sum[i][k+i-1][0])%19650827;
            if(a[i+k]>a[i+k-1])sum[i][i+k][1]=(sum[i][i+k][1]+sum[i][k+i-1][1])%19650827;
        }
    printf("%lld\n",(sum[1][n][0]+sum[1][n][1])%19650827);
    return 0;
}