51nod 1370 排列与操作

1370 排列与操作

题目来源：  TopCoder

基准时间限制：2 秒 空间限制：131072 KB 分值: 320  难度：7级算法题

 收藏

 关注

给定N长排列P，其中排列指数集{1,2,3...N}组成的一个序列，序列中每个元素恰好出现一次。初始时这个排列是给出的。之后你可以进行不超过K次操作（也就是说你可以操作0次，1次..K次），每次操作如下：
1）选择一个连续的非空的子区间[L,R]，其对应元素为{P[L],P[L+1],..，P[R]}；
2）设这个区间元素最大值为MAX，测将这个区间的所有元素都重新赋值为MAX。
问在K次以内的操作中，你一共能构造出多少种不同的序列出来，输出这个结果 modulo1,000,000,007后的结果。

注意：两个序列A，B不同是指存在元素位置下标 i，满足A[i]!=B[i].
提示：样例中第2个小数据可以构造的4组结果包括:(3, 1, 2),(3, 2, 2),(3, 3, 2),(3, 3, 3).

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=3。每组测试数据有相同的结构构成。每组数据的第一行包含两个整数N，K，其中1<=N<=200,0<=K<=200。接下来N行每行一个整数Pi，表示排列P中第i个元素，保证1~N各出现一次。

Output

每组数据一行输出，即能构造的不同序列个数mod 10^9+7后的结果。

Input示例

32 112 3 2 3 1 2 4 2 4 3 2 1

Output示例

2413

孔炤  (题目提供者)

C++的运行时限为：2000 ms ，空间限制为：131072 KB  示例及语言说明请按这里

【分析】

DP

dp[i][j][k]表示前i个数字，当前序列位置为j，共操作k次得到的序列方案数

需要前缀和优化

【代码】

//51nod1370 排列与操作 
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mod=1e9+7;
const int mxn=205;
int T,n,m;
int dp[mxn][mxn][mxn];
int p[mxn],pre[mxn],nxt[mxn],s[mxn][mxn];
inline int solve()
{
	int i,j,k,x;
	scanf("%d%d",&n,&m);
	memset(dp,0,sizeof dp);
	fo(i,1,n) scanf("%d",&p[i]);
	dp[0][0][0]=1;
	p[0]=p[n+1]=n+1;
	fo(i,1,n)
	{
		j=i;while(p[j-1]<p[i]) j--;pre[i]=j;
		j=i;while(p[j+1]<p[i]) j++;nxt[i]=j;
	}
	fo(i,1,n)
	{
		memset(s,0,sizeof s);
		fo(k,0,min(i,m)) fo(j,0,nxt[i])
		  s[k][j+1]=(s[k][j]+dp[i-1][j][k])%mod;
		fo(j,pre[i],nxt[i])
		{
		    fo(k,1,min(i,m))
		    {
		  	    if(j!=i)
		  	  	  dp[i][j][k]=(dp[i][j][k]+s[k-1][j]-s[k-1][pre[i]-1])%mod;
			    else
				  dp[i][j][k]=(dp[i][j][k]+s[k-1][j-1]-s[k-1][pre[i]-1])%mod;
//		  	  if(j!=i) fo(x,pre[i]-1,j-1)
//				dp[i][j][k]=(dp[i][j][k]+dp[i-1][x][k-1])%mod;
//		  	  else fo(x,pre[i]-1,j-2)
//		  	    dp[i][j][k]=(dp[i][j][k]+dp[i-1][x][k-1])%mod;
		    }
		}
		fo(k,0,min(i,m))
		  dp[i][i][k]=(dp[i][i][k]+dp[i-1][i-1][k])%mod;
		fo(j,0,n) fo(k,0,min(i-1,m))
		  dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
	}
	int ans=0;
	fo(i,0,m) ans=(ans+dp[n][n][i])%mod;
	return (ans+mod)%mod;
}
int main()
{
	int i,j;
	scanf("%d",&T);
	while(T--)
	  printf("%d\n",solve());
	return 0;
}
/*
1
2 1
1 2
*/