[记忆化搜索] 交换

问题描述

给定一个 $0,1,2,\dots ,n-1$ 的排列 $p$。
注意给定的 $p$ 可以不是由小到大排列，但一定是 $0\sim n-1$ 的 $n$ 个不相同的数。
对于一个包含 $0,1,2,\dots ,n-2$ 这些数的排列 $q$，其想要被认为是优美的排列，当且仅当 $q$ 满足以下条件：
对排列 $s=0,1,\dots ,n-1$ 进行 $n-1$ 次交换。

1. 交换 $s_{q0},s_{q0+1}$
2. 交换 $s_{q1},s_{q1+1}$
   $\dots$
   最后能使得排列 $s=p$。
   问有多少个优美的排列，答案对 $10^9+7$ 取模。

题意简述：
对于固定排列顺序的 $s=0,1,2,\dots ,n-1$ ，问有多少种排列 $q$ ，可以将 $s$ 按上述方式进行 $n-1$ 次变换后，变为指定输入的排列 $p$ 。

输入格式

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

输出格式

输出一行表示答案。

样例

样例输入1：

3
1 2 0

样例输出1：

1

数据范围

对于 $30\%$ 的数据，$2\le n\le 10$。
对于 $100\%$ 的数据，$2\le n\le 50$。

题解

对于 $30\%$ 的数据，直接暴力枚举 $q_i$，复杂度为 $\mathrm{O}(2^n)$。

对于 $100\%$ 的数据，由于正着不好考虑，考虑倒着处理。
将 $p$ 变回 $0,1,2,\dots ,n-1$ 的状态，最后一次交换 $(p,p+1)$，在 $p$ 前面的数到不了后面，所以左边的数连续，右边的数连续。
考虑使用记忆化搜索，用 $d{p}_{i,j}$ 表示从 $i$ 到 $j$ 的序列的优美序列个数。
枚举相邻元素 $(p,p+1)$，判断前面和后面是否连续，是的话 $d{p}_{x,y}+=d{p}_{x,p}\times d{p}_{p+1,y}\times C_{y-x-1}^{p-x}$。

#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long n;
long long a[60];
long long dp[60][60];
long long zh[60][60];
//杨辉三角预处理 C(i, j)
void solve(){
zh[0][0] = 1;
for(long long i = 1; i <= n; ++ i){
zh[i][0] = 1;
zh[i][i] = 1;
for(long long j = 1; j < i; ++ j){
zh[i][j] = zh[i - 1][j] + zh[i - 1][j - 1];
zh[i][j] %= mod;
}
}
}
long long dfs(long long x, long long y){
if(x == y){
dp[x][y] = 1;
return 1;
}
//记忆化
if(dp[x][y]){
return dp[x][y];
}
//枚举 p
for(long long i = x; i < y; ++ i){
bool f = 1;
swap(a[i], a[i + 1]);
//判断 x 到 p
for(long long j = 1; j <= i; ++ j){
if(a[j] > i || a[j] < 1){
f = 0;
break;
}
}
//判断 p + 1 到 y
for(long long j = i + 1; j < y; ++ j){
if(a[j] > y || a[j] < i + 1){
f = 0;
break;
}
}
if(f){
//转移
dp[x][y] += (dfs(x, i) * dfs(i + 1, y) % mod) * zh[y - x - 1][i - x] % mod;
dp[x][y] %= mod;
}
swap(a[i], a[i + 1]);
}
return dp[x][y];
}
int main(){
//输入
scanf("%lld", &n);
for(int i = 1; i <= n; ++ i){
scanf("%lld", &a[i]);
a[i] ++;
}
solve();
dfs(1, n);
printf("%lld", dp[1][n]); 
return 0;
}

原文地址：https://blog.csdn.net/m0_64542522/article/details/142529154

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！