【AtCoder】【DP】【思维】Prefix Median（AGC012）

模的是这位神犇的代码：Atcoder AGC012F : Prefix Median

题意：

在动态中位数那道题上做了一些改动。给你一个序列a，可以将a重新任意排序，然后对于a序列构造出b序列。

假设a序列有2*n-1个元素，b序列有n个元素。

其中b[i]=Median(a[1],a[2],a[3]...a[2i-1])。求能够构造出多少个不同的b序列。

数据范围：

1<=N<=50,1<=ai<=2N-1

思路：

这道题真的是究极神题...虽然说代码实现比较简单，但是分析的过程是恶心到吐的。

首先，我们需要分析一堆性质：

首先将a序列排序，便于讨论

\(a[i]<=b[i]<=a[2*N-i]\)
\(当i<j时，不存在i使得：b[j]<b[i]<b[j+1]或者是b[j+1]<=b[i]<=b[j]\)

先抛开性质不谈，首先有很明显的一个性质：i从左往右走的时候，假设已经选取的元素的集合为c(c是排好了序的)。每加入两个元素，b[i]的取值的下标在c中只会向左或者是向右移动一格，或者是保持不变。（可以通过枚举法简单证得，即新加入的两个元素x,y都小于b[i-1],或者是都大于b[i+1]，或者是一个大于，一个小于的情况）。

然后来看上面的性质。因为求b[i]时的序列中小于等于b[i]至少有i个元素，大于等于b[i]的至少有i个元素，所以说在a数组中的b[i]至少在a[i]~a[2N-i]之间。性质1是没有问题的；

然后是性质2。因为最开始所说的“明显的性质”，所以说b[j]与b[j+1]在已经选取的数字的序列之的位置相差不会超过1，也就是说中间不会间隔任何的数字。但同时还需要注意一点，就是这里是'<'和'>'，也就是说是可以取等的，也就是位置保持不变的情况。那么性质2也有了。

接下来就是怎么实现了。

由于开头赋的题解对于代码的部分的具体细节解释的不是很详细，我这里就贸然做一些补充了(〃'▽'〃)

首先定义状态dp[i][L][R]表示现在确定的是b[i]，可选元素中小于等于b[i+1]的有L个，大于b[i+1]的有R个。然后考虑转移。转移的话就是枚举b[i]选取的位置，然后删去相应的元素就可以了。然而并没有这么简单！！！具体细节将在代码中进行详细的说明。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100

#define MO 1000000007

using namespace std;

typedef long long LL;

int a[MAXN+5],n;

LL f[MAXN+5][MAXN+5][MAXN+5];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=2*n-1;i++)

		scanf("%d",&a[i]);

	sort(a+1,a+2*n);

	f[n][1][0]=1;

	//初始状态中，小于等于b[n]的有1个，大于b[n]的有0个（虽然稍微有些违背定义，但是暂且先这样定义吧）

	LL t;

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

	{

		int al=(a[i]!=a[i+1]),ar=(a[2*n-i]!=+a[2*n-i-1]);

		//这里是向两边进行扩展，也就是运用性质1进行扩展

		//因为相同的数进行的扩展是没有意义的，所以说需要这样进行能否进行有效的扩展的判断

		for(int l=0;l<=2*n-1;l++)

			for(int r=0;l+r<=2*n-1;r++)

				if(f[i+1][l][r])

				{

					t=f[i+1][l][r];

					for(int dl=1;dl<=l+al;dl++)//选择小于b[i+1]的元素

					{

						f[i][l+al-dl+1][r+ar+(dl>1)]+=t;

						//+al是进行对于L的拓展

						//-dl是删去选了的元素与b[i+1]之间的元素

						//+1是因为删多了一个，那就是已经选取的b[i]，所以说要加回来

						//右边+(dl>1)是因为：

						//当dl==1的时候，选取的就是b[i+1]这个元素，那就是什么都不会改变的

						//当dl>1的时候，选取的就是<b[i+1]中的一个元素，那么b[i+1]就会成为>b[i]中的一个元素，又因为可以取整，所以说要加上去

						f[i][l+al-dl+1][r+ar+(dl>1)]%=MO;

					}

					for(int dr=1;dr<=r+ar;dr++)//选择大于等于b[i+2]的元素

					{

						f[i][l+al+1][r+ar-dr]+=t;

						//左边+1是因为加入b[i]这个可选元素，与上面的比较类似

						//右边就是正常的转移，这还比较简单

						f[i][l+al+1][r+ar-dr]%=MO;

					}

				}

	}

	LL ans=0;

	for(int l=0;l<=2*n-1;l++)

		for(int r=0;l+r<=2*n-1;r++)

			ans=(1LL*ans+1LL*f[1][l][r])%MO;//对于每一个可能的情况都需要计算答案

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

	return 0;

}

以上只是个人的理解，如果出了什么偏差，还请读者自行脑补ヽ(･ω･´ﾒ)

巴特西

【AtCoder】【DP】【思维】Prefix Median（AGC012）

题意：

数据范围：

思路：

代码：

最新文章

热门文章