[CSP-S模拟测试]:毛二琛（DP）

题目描述

　　$MYC$在$NOI2018$中，遇到了$day1T2$这样一个题，题目是让你求有多少“好”的排列。$MYC$此题没有获得高分，感到非常惭愧，于是回去专心研究排列了。如今数排列的题对$MYC$来说已经是小菜一碟了。于是$MYC$想考考你，扔给你了一个非常$naive$的数排列题给你。
　　给定一个$\{0,1,2,3,...,n-1\}$的排列$p$。一个$\{0,1,2,...,n-2\}$的排列$q$被认为是优美的排列，当且仅当$q$满足下列条件：
　　对排列$s=\{0,1,2,3,...,n-1\}$进行$n–1$次交换。
　　$1.$交换$s[q_0],s[q_0+1]$
　　$2.$交换$s[q_1],s[q_1+1]$
　　...
　　最后能使得排列$s=p$。
　　问有多少个优美的排列，答案对$10^9+7$取模。

原题见：$SRM517-600$

输入格式

第一行一个正整数$n$。
第二行$n$个整数代表排列$p$。

输出格式

仅一行表示答案。

样例

样例输入：

3
1 2 0

样例输出：

数据范围与提示

样例解释：

$q=\{0,1\}\{0,1,2\}\rightarrow\{1,0,2\}\rightarrow\{1,2,0\}$
$q=\{1,0\}\{0,1,2\}\rightarrow\{0,2,1\}\rightarrow\{2,0,1\}$

数据范围：

$20\%$：$n\leqslant 10$
$50\%$：$n\leqslant 50$
$70\%$：$n\leqslant 300$
$100\%$：$n\leqslant 5,000$

题解

题目可以转化为：一个大小为$n-1$的排列，某些地方限制了相邻两数的大小关系，求方案数。

考虑$DP$，设$dp[i][j]$表示进行到了第$i$个数，第$i$个数在前$i$个数中是第$j$小的方案数。

可以预处理出来哪些位置需要往左或右移即可。

注意一些限制，以向左移为例，第$i$次交换的位置要在第$i-1$次交换之前，反之同理。

这样做出来时间复杂度是$\Theta(n^3)$的，前缀和优化即可。

因为数据点没有给不满足的情况，所以下面代码中没有判不满足的情况，即$pos_i=i$。

时间复杂度：$\Theta(n^2)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=1000000007;

int n;

int a[5001];

bool com[5001];

long long dp[5001][5001],g[5001][5001];

long long ans;

int main()

{

	scanf("%d",&n);

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

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

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

		if(i<a[i]){com[i-1]=1;com[a[i]-1]=1;}

		else for(int j=a[i];j<i-1;j++)com[j]=1;

	dp[0][1]=g[0][1]=1;

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

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

		{

			if(com[i-1])dp[i][j]=(dp[i][j]+g[i-1][i]-g[i-1][j-1]+mod)%mod;

			else dp[i][j]=(dp[i][j]+g[i-1][j-1])%mod;

			g[i][j]=(g[i][j-1]+dp[i][j])%mod;

		}

	for(int i=1;i<n;i++)ans=(ans+dp[n-2][i])%mod;

	printf("%lld",ans);

	return 0;

}

rp++

myc