CF2051G Snakes 题解

n \le 20

，很小，显然可以状压 dp。

注意到，操作过程中蛇的顺序保持不变，因此问题本质上是求一个 $\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 通过记录

文章操作

代码

相关推荐

评论

CF2051G Snakes 题解