排列DP - 洛谷保存站

# 排列DP

$a_1$到$a_n$，n个数，写下来，就是排列

一般问的是：所有排列中，满足某个要求的排列个数。

## 题

### 题面

1~n所有排列中，逆序对个数为偶数的有多少个？

### 一般思路

把n个数按从小到大或从大到小插入。

### 此题思路

按从小到大插入。

${f_i}_j$代表当前已经把$1$~$i$插入了，逆序对个数为j的方案数为多少。

已插入到$i$，要插入$i+1$。

那么可以插入到$a_1$之前，$a_i$之后，那么我们给每一个可插入位置编一个号，$0$~$i$。

如果插入到最前面，逆序对增加$i$，插入到第一个位置，逆序对增加$i-1$,插入到第二个位置，逆序对增加$i-2$……以此类推，插入最后一个位置，逆序对增加$0$。

那么转移方程就是：

${f_{i+1}}_{j+i-k}+={f_{i}}_{j}$(k为插在哪个位置）。
```cpp
int f[i][j];//1~i已经插入此时有j个逆序对的方案数

int main(){
	cin >> n;
	f[1][0] = 1;
	for(int i = 1;i < n;++ i)
		for(int j = 0;j <= i*(i-1)/2;++ j)//i个数最多形成i*(i-1)/2个逆序对
			//插入i+1
			for(int k = 0;k <= i;++ k)//i+1要插入到第k个位置
				f[i+1][j+i-k] += f[i][j]; 
	int ans = 0;
	for(int j = 0;j <= n*(n-1)/2;j += 2)
		ans += f[n][j];
	cout << ans << endl;
	return 0;
} 
```
### 优化1
```cpp
int f[i][j];//1~i已经插入此时有j个逆序对的方案数
//j = 0 偶数个 
//j = 1 奇数个

int main(){
	cin >> n;
	f[1][0] = 1;
	for(int i = 1;i < n;++ i)
		for(int j = 0;j < 2;++ j)//插入i+1
			for(int k = 0;k <= i;++ k)//i+1要插入到第k个位置
				f[i+1][(j+i-k)%2] += f[i][j]; 
	int ans = f[n][0];
	cout << ans << endl;
	return 0;
} 
```
## 题2

### 题面

$1$到$n$，$n$个数，定义一个数的激动值为有多少个数比它前面的都大，问$1$到$n$所有排列中有多少个数的激动值为$k$?

### 思路

按从大到小插入。

转移方程：

1.${f_{i-1}}_{j+1} += {f_i}_j$

2.${f_{i-1}}_j += {f_i}_j*(n-i+1)$

正在渲染内容...