swap(2018.10.16)

题意：给定一个{0,1,2,3,…,n-1}的排列 p。

一个{0,1,2 ,…,n-2}的排列 q 被认为是优美的排列，

当且仅当 q 满足下列条件对排列 s={0,1,2,3,...,n-1}进行 n–1 次交换。

交换 s[q0],s[q0+1]
交换 s[q1],s[q1+1]

…

最后能使得排列 s=p. 问有多少个优美的排列，答案对 10^9+7 取模。

( n<=5000)

题解：这个题我们首先要知道一个性质，p排列的每一个数都是s排列经过变换后的最后状态，我们就能通过这些推出q数组中一些数的先后顺序

然后通过这些我们就可以做dp了，f[i][j]表示前i个数，第i个数在前i个数中是第j小的。前缀和优化。时间复杂度：\(O(n^2)\)

我讲的可能不是太好，安利机房一位学长的一篇博客：大佬的博客

#include<cstdio>

#include<algorithm>

using namespace std;

int n,p[5001],ans,pos[5001],mod=1e9+7,f[5001][5001],g[5001][5001];

int main()

{

	scanf("%d",&n);

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

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

		if(p[i]>i)

		{

			if(i>1)if(pos[i-1]==1){printf("0\n");return 0;}else pos[i-1]=2;

			for(int j=i;j<p[i]-1;j++)if(pos[j]==2){printf("0\n");return 0;}else pos[j]=1;

			if(p[i]-1<=n-2)if(pos[p[i]-1]==1){printf("0\n");return 0;}else pos[p[i]-1]=2;

		}

		else if(p[i]<i)

		{

			if(p[i]>1)if(pos[p[i]-1]==2){printf("0\n");return 0;}else pos[p[i]-1]=1;

			for(int j=p[i];j<i-1;j++)if(pos[j]==1){printf("0\n");return 0;}else pos[j]=2;

			if(i-1<=n-2)if(pos[i-1]==2){printf("0\n");return 0;}else pos[i-1]=1;

		}

	f[1][1]=g[1][1]=1;

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

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

		{

			if(pos[i-1]==1)f[i][j]=(f[i][j]+g[i-1][j-1])%mod;

			if(pos[i-1]==2)f[i][j]=((f[i][j]+g[i-1][i-1]-g[i-1][j-1])%mod+mod)%mod;

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

		}

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

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

}

巴特西

swap(2018.10.16)

最新文章

热门文章