题目

BZOJ传送门= ̄ω ̄=
LUOGU传送门= ̄ω ̄=

题目描述

题目描述

输入格式

输入格式

输出格式

输出格式

样例输入

4
1701 1702 1703 1704

样例输出

8

题解

基础区间DP,要注意题意是前一个入队的人和当前的人比,不是队的右端和当前的人比……(窝就被坑了)。
所以我们设:$f[i,j,p]$(p=0或1)为区间为$[l,r]$,当前要把这个人插入到左端(p=0)或右端(p=1)时有多少种不同解。
然后$arr[i]$表示第i个人的高度
所以可以得到这个递推式:
$f[i,j,0]=f[i,j-1,0]×(arr[j]>arr[i])+f[i,j-1,1]×(arr[j]>arr[j-1])$
$f[i,j,1]=f[i+1,j,0]×(arr[i]<arr[i+1])+f[i+1,j,1]×(arr[i]<arr[j])$

注意!$f[i,i,0]=1,f[i,i,1]=0$!或者$f[i,i,1]=1,f[i,i,0]=0$也行!不然会重复计算!

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename tp>void read(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
typedef long long LL;
LL n,arr[1005],f[1005][1005][2];
bool book[1005][1005][2];
LL dfs(LL l,LL r,LL p)
{
    if(l==r)return p?1:0;
    if(book[l][r][p])return f[l][r][p];
    book[l][r][p]=1;
    if(p)
        f[l][r][p]+=dfs(l,r-1,0)*(arr[r]>arr[l]),
        f[l][r][p]+=dfs(l,r-1,1)*(arr[r]>arr[r-1]);
    else
        f[l][r][p]+=dfs(l+1,r,0)*(arr[l]<arr[l+1]),
        f[l][r][p]+=dfs(l+1,r,1)*(arr[l]<arr[r]);
    return f[l][r][p]%19650827;
}
int main()
{
    read(n);
    for(LL i=1;i<=n;read(arr[i++]));
    printf("%lld\n",(dfs(1,n,0)+dfs(1,n,1))%19650827);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *