1996: [Hnoi2010]chorus 合唱队

2022-12-05 20:49:18

链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1996

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

HINT

题解：还是一个区间动归，可是这道题的问题在于比较难想到怎么去设，我们会发现每次放一个数时我们都会

考虑放在左边还是放在右边，实际上最后数放在左边还是右边的方案数是不同的，所以我们除了枚举区间，还要枚举当前这个数是放在了左边还是放在了右边，先来结合动态转移方程看一看：

if (a[j]>a[i]) f[i][j][1]+=f[i][j-1][0];
if (a[j]>a[j-1]) f[i][j][1]+=f[i][j-1][1];
if (a[i]<a[j]) f[i][j][0]+=f[i+1][j][1];
if (a[i]<a[i+1]) f[i][j][0]+=f[i+1][j][0];

（是不是看着觉得很莫名其妙？别急，解释一下。）我们用f[i][j][0]表示构成区间i~j有多少种可能，且这个区间最后一个被放进的数存在最左边，即i处，同理，f[i][j][1]表示最后一个被放进的数存在最右边，即j处。a数组则用来存储这个队列。

先来看第一个式子

if (a[j]>a[i]) f[i][j][1]+=f[i][j-1][0];这个式子的意思是，我们设当前i~j区间最后一个数放在了最右边即a[j]，则上一个区间为f[i][j-1],我们又设上一次区间的最后一个数放在了f[i][j-1]的左边即a[i],那么上一次的方案数即为f[i][j-1][0],我们判断这种方案成立的方法即为如果这次的这个数被放在了最右边，那么它是大于上一次的数，即a[j]需大于a[i],如果大于，那么这种方案就成立，就可以加上这种方案数。如图：

这么左右左右去枚举一下总共有四种可能，这就是为什么上面有四个方程式。

具体看程序吧：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int ans,n,j,a[],f[][][];//我刚开始数组没开对，调了很久，最后一个一定要设为2而不是1;

int main()

{

   scanf("%d",&n);

   for (int i=;i<=n;i++) scanf("%d",&a[i]);

   memset(f,,sizeof(f));

   for (int i=;i<=n;i++) f[i][i][]=;//刚开始构成单个的方案数皆为一

   for (int len=;len<=n;len++)//枚举长度

    for (int i=;i<=n-len+;i++)

//这两句for循环其实等同于

  for (int i=n;i>=;i--)

  for (int j=i;j<=n;j++)

    {

      j=i+len-;

      if (a[j]>a[i]) f[i][j][]+=f[i][j-][];

      if (a[j]>a[j-]) f[i][j][]+=f[i][j-][];

      if (a[i]<a[j]) f[i][j][]+=f[i+][j][];

      if (a[i]<a[i+]) f[i][j][]+=f[i+][j][];//之前解释过的动态转移方程

      f[i][j][]%=;

      f[i][j][]%=;//题目要求

    }

   ans=(f[][n][]+f[][n][])%;//答案是左右之和

   printf("%d\n",ans);

   return ;

}

（咳咳，我看了半天人家的题解）

码农公寓