洛谷 P3205 [HNOI2010]合唱队 题解【区间DP】【分类讨论】

作者: wjyyy 分类: DP,区间DP,解题报告 发布时间: 2018-07-15 15:30

点击量:26

 

   区间DP+分类讨论

 

题目描述

为了在即将到来的晚会上有更好的演出效果,作为AAA合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共N个人,第i个人的身高为Hi米(1000<=Hi<=2000),并已知任何两个人的身高都不同。假定最终排出的队形是A 个人站成一排,为了简化问题,小A想出了如下排队的方式:他让所有的人先按任意顺序站成一个初始队形,然后从左到右按以下原则依次将每个人插入最终棑排出的队形中:

 

-第一个人直接插入空的当前队形中。

 

-对从第二个人开始的每个人,

 

  • 如果他比前面那个人高(H较大),那么将他插入当前队形的最右边。
  • 如果他比前面那个人矮(H较小),那么将他插入当前队形的最左边。

 

当N个人全部插入当前队形后便获得最终排出的队形。

 

例如,有6个人站成一个初始队形,身高依次为1850、1900、1700、1650、1800和1750,

 

那么小A会按以下步骤获得最终排出的队形:

 

  • 1850
  • 1850,1900 因为1900>1850
  • 1700,1850,1900 因为1700<1900
  • 1650,1700,1850,1900 因为1650<1700
  • 1650,1700,1850,1900,1800 因为1800>1650
  • 1750,1650,1700,1850,1900,1800 因为1750<1800

 

因此,最终排出的队形是 1750,1650,1700,1850,1900,1800

 

小A心中有一个理想队形,他想知道多少种初始队形可以获得理想的队形

输出格式:

注意要mod19650827

 

输入输出样例

输入样例#1:
4
1701 1702 1703 1704
输出样例#1:
8

说明

30%的数据:n<=100

 

100%的数据:n<=1000

 

题解:

   一道基础的区间DP,不过要分类讨论。设f[i][j][0]为构成区间[i,j]的方案数且最后一个插入的数为最左端一个;f[i][j][1]为最右端一个。

 

   因为状态转移与上一状态的最后一个数在左还是右有关系,所以要分情况讨论。也就是说,一个区间可以由2×2个状态转移过来,分别是最左边的小于最右边的,最左边的小于次左边的,最右边的大于最左边的,最右边的大于次右边的。不过要注意的是,初始值只能赋给单点的其中一个状态,不然长度为2时的区间DP就会有4个状态转移,实则只有两个。

 

Code:

#include<cstdio>
#include<cstring>
#define p 19650827
int a[1001];
int f[1001][1001][2];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i][i][0]=1;
    }
    for(int i=1;i<n;i++)//长度
        for(int j=1;j<=n-i;j++)//左端
        {
            if(a[j]<a[j+1])//各种情况
                f[j][j+i][0]+=f[j+1][j+i][0];
            if(a[j]<a[j+i])
                f[j][j+i][0]+=f[j+1][j+i][1];
            if(a[j+i]>a[j])
                f[j][j+i][1]+=f[j][j+i-1][0];
            if(a[j+i]>a[j+i-1])
                f[j][j+i][1]+=f[j][j+i-1][1];
            f[j][j+i][0]%=p;
            f[j][j+i][1]%=p;
        }
    printf("%d\n",(f[1][n][0]+f[1][n][1])%p);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */