【BZOJ4621】Tc605

Description

最初你有一个长度为 N 的数字序列 A。为了方便起见，序列 A 是一个排列。

你可以操作最多 K 次。每一次操作你可以先选定一个 A 的一个子串，然后将这个子串的数字全部变成原来这个子串的最大值。问最终有几种可能的数字序列。答案对 1e9+7 取模。

Input

第一行两个数 N 和 K。第二行 N 个数，描述一个排列 A。

N,K<=500，

有6组数据N>100，有梯度

Output

输出一个数，表示答案在模域下的值。

Sample Input

3 2
3 1 2

Sample Output

题解：好题。

先预处理出每个数左边和右边第一个比它大的数的位置ls,rs，然后将这个数看成一个区间，问题就变成了选出一些区间覆盖整个序列的方案数。用f[i][j]表示覆盖到位置i，已选择了j个区间的方案数。那么对于所有ls<=i<=rs，用$\sum\limits_{k=ls-1}^{i-1}f[k][j-1]$更新即可，显然可以用前缀和优化。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int P=1000000007;

int n,m,ans,sum;

int f[510][510],v[510];

int main()

{

	scanf("%d%d",&n,&m);

	int i,j,k,ls,rs;

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

	f[0][0]=1;

	for(i=1;i<=n;i++)

	{

		for(ls=i;ls>1&&v[ls-1]<v[i];ls--);

		for(rs=i;rs<n&&v[rs+1]<v[i];rs++);

		for(j=m;j>=0;j--)

		{

			f[i][j]=(f[i][j]+f[i-1][j])%P;

			if(j)

			{

				sum=0;

				for(k=ls;k<=rs;k++)	sum=(sum+f[k-1][j-1])%P,f[k][j]=(f[k][j]+sum)%P;

				f[i][j]=(f[i][j]-f[i-1][j-1]+P)%P;

			}

		}

	}

	for(i=0;i<=m;i++)	ans=(ans+f[n][i])%P;

	printf("%d",ans);

	return 0;

}//3 2 1 2 3

巴特西

【BZOJ4621】Tc605 DP