P13792
EnjoySilence
·
·
题解
题意简述：有 n 张五种花色的牌 S,W,E,R,C，其中花色 C 的牌是王牌。每次操作可以将一张牌插入两张牌之间，需要确定一种花色间的顺序，使得在进行若干次操作后，整副牌的花色按照该种顺序排列，且同一花色内的牌按照数字大小升序排序，特别地，王牌花色需要排在最后一个。求最小的操作次数。
**思路**：考虑将“插入操作”当做“删除操作”，因为在最优策略下，一张牌一定在一次插入后就不会第二次进行插入，且不会对剩余牌造成影响，等价于直接删除。
题目中需要按照某种顺序排列花色，观察到需要排序的花色数量极其少，只有 $4$ 种，因此直接考虑 $4!$ 暴力枚举全排列。
由于需要以花色和数字为关键字对牌进行排序，因此考虑将这两个要素融合成牌的一个权重，依据权重进行升序排序。不难想到用花色在全排列中的位次 $\times n$ 后加上数字作为权重，这样既兼顾了花色的升序，又兼顾了数字的升序，还能避免不同花色间串号（因为 $V\le n$，所以不同花色间的权重一定不会串）特别地，需要保证花色为 `C` 的牌权重为 $4n+V$，保证王牌花色的牌的权重高于其他花色的一切牌。
因为我们需要最小化删除的牌个数，又要使得所有牌的权重升序排序，所以考虑在权重数组 $w$ 上求 LIS 得到长度 $l$ 后用 $n-l$ 得到最小删除数量，只需要在所有排列中求出 $n-l$ 的最小值并输出即可。
枚举全排列并修改权重的时间复杂度为 $\mathcal O(4!n)$，求出 LIS 的时间复杂度为 $\mathcal O(4!n\log n)$，因此时间复杂度取 $\mathcal O(n\log n)$，可以通过本题。
**AC CODE**：
[submission](https://www.luogu.com.cn/record/304797927)。
```cpp
#include<bits/stdc++.h>
#define y0 y_0
#define y1 y_1
#define fi first
#define se second
#define endl '\n'
#define vec vector
#define em emplace
#define pb push_back
#define eb emplace_back
#define lc(x) x << 1
#define rc(x) x << 1 | 1
#define lowbit(x) ((x) & (-(x)))
#define popcount(x) __builtin_popcount(x)
#define ckmin(x, y) x = (x) <= (y) ? (x) : (y)
#define ckmax(x, y) x = (x) >= (y) ? (x) : (y)
#define debug(x) cerr << #x << " = " << x << endl
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
// #define MultiTest
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 5;
int n, w[N], d[N];
pii c[N];
int get(char ch) {
switch(ch) {
case 'S': return 1;
case 'W': return 2;
case 'E': return 3;
case 'R': return 4;
case 'C': return 5;
}
}
int getLIS() {
memset(d, 0x3f, sizeof d);
int len = 0;
d[0] = 0;
for(int i = 1; i <= n; i++) {
if(w[i] > d[len]) d[++len] = w[i];
else {
int x = lower_bound(d + 1, d + 1 + len, w[i]) - d;
d[x] = w[i];
}
}
return len;
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) {
char ch; cin >> ch;
int num; cin >> num;
c[i] = {get(ch), num};
if(c[i].fi == 5) w[i] = 4 * n + num;
}
int p[5] = {0, 1, 2, 3, 4}, maxlis = 0;
do {
for(int i = 1; i <= 4; i++) {
for(int j = 1; j <= n; j++) {
if(c[j].fi == p[i]) w[j] = (i - 1) * n + c[j].se;
}
}
ckmax(maxlis, getLIS());
} while(next_permutation(p + 1, p + 5));
cout << n - maxlis << endl;
}
int main() {
IOS;
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
int T = 1;
#ifdef MultiTest
cin >> T;
#endif
while(T--)
solve();
return 0;
}
```