CF2051G Snakes 题解
Mier_Samuelle
·
·
题解
注意到，操作过程中蛇的顺序保持不变，因此问题本质上是求一个 **$\bm n$ 条蛇的排列**。
首先我们考虑，如果排列已经确定，如何求出最右侧蛇右端点的最小编号？
要求出这个值，我们只需要求出每相邻两条蛇之间的 **最小安全距离**（也就是使两条蛇不相撞的最短距离），然后全部加在一起即可。
我们记蛇 $i$ 右移的次数为 $a_i$，左移的次数为 $b_i$，那么显然蛇 $i,j$ 的最小安全距离 $d_{i,j}$ 为：**整个操作过程** 中 $a_i-b_j+1$ 的最大值（蛇 $i$ 在蛇 $j$ 左侧）。
求 $d_{i,j}$ 的这个部分可以在转移前预处理，时间复杂度 $O(qn)$，空间复杂度 $O(n^2)$。
然后就可以 dp 了。
定义状态 $dp_{S,i}$ 为：已经压入了集合 $S$ 中的蛇，且最后压入的是蛇 $i$，此时最右侧蛇右端点的最小编号。
状态转移方程：$dp_{S,i}=\min\limits_{j=1}^n\lbrace dp_{S',j}+d_{j,i} \rbrace$，其中 $S'=\lbrace x|x \in S,x \ne i \rbrace$。初值和答案见代码。
dp 部分时间复杂度 $O(2^n \cdot n^2)$，空间复杂度 $O(2^n \cdot n)$。
### 代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 30, MAXQ = 2e5 + 10, MAXS = 1 << 20;
int f[MAXN][MAXN], dp[MAXS][MAXN], cnta[MAXN], cntb[MAXN];
signed main(){
int n, q;
cin >> n >> q;
for (int i = 0;i <= n - 1;i++)
for (int j = 0;j <= n - 1;j++) f[i][j] = 1;
while (q--){
int ind;
char opt;
cin >> ind >> opt;
ind--;
cnta[ind] += (opt == '+');
cntb[ind] += (opt == '-');
for (int i = 0;i <= n - 1;i++){
f[ind][i] = max(f[ind][i], cnta[ind] - cntb[i] + 1);
f[i][ind] = max(f[i][ind], cnta[i] - cntb[ind] + 1);
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 0;i <= n - 1;i++) dp[1 << i][i] = 1; //从编号为 1 的格子开始放蛇
for (int st = 0;st <= (1 << n) - 1;st++){
for (int i = 0;i <= n - 1;i++){
if (!(st >> i & 1)) continue;
for (int j = 0;j <= n - 1;j++){
if (!(st >> j & 1)) continue;
dp[st][i] = min(dp[st][i], dp[st - (1 << i)][j] + f[j][i]);
}
}
}
int ans = 9e18;
for (int i = 0;i <= n - 1;i++) ans = min(ans, dp[(1 << n) - 1][i] + cnta[i]); //还需要加上最后一条蛇右移的格数
cout << ans << endl;
return 0;
}
```
[CF 通过记录](https://codeforces.com/contest/2051/submission/305571592)