题目分析

不是很难的区间dp,用l[i][j]表示i到j这端最后插入的是a[i]的方案数,r[i][j]则表示i到j这端最后插入的是a[j]的方案数,就很容易推出状态转移方程:

l[i][j]=l[i+1][j](a[i+1]>a[i])+r[i+1][j](a[j]>a[i]);
r[i][j]=l[i][j-1](a[i]<a[j])+r[i][j-1](a[j-1]<a[j]);

然后初始化是l[i][i]=1(或者r[i][i]=1;但是不可以两个都等于1,不然会重复计算)

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,a[1005],mod=19650827;
int l[1005][1005],r[1005][1005];
int main()
{
    int i,j;
    n=read();
    for(i=1;i<=n;i++)a[i]=read();
    for(i=1;i<=n;i++)l[i][i]=1;
    for(i=n;i>=1;i--)
        for(j=i+1;j<=n;j++){
        if(a[i+1]>a[i])l[i][j]+=l[i+1][j];
        if(a[j]>a[i])l[i][j]+=r[i+1][j];
        l[i][j]%=mod;
        if(a[j]>a[i])r[i][j]+=l[i][j-1];
        if(a[j]>a[j-1])r[i][j]+=r[i][j-1];
        r[i][j]%=mod;
    }
    printf("%d",(l[1][n]+r[1][n])%mod);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

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

你是机器人吗? =。= *