专栏文章

P6946 [ICPC2018 WF] Go with the Flow 题解

LLJY_ljy
P6946题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mir07adc
此快照首次捕获于
2025/12/04 13:36
3 个月前
此快照最后确认于
2025/12/04 13:36
3 个月前
查看原文
updated on 2025.4.12: 感谢 @yellow_mt 提醒，已经将 49 行代码修改。
本代码需要开 -O2 优化通过。
考虑枚举行宽后模拟。
由于符合条件的行宽的范围为 [max⁡1≤i≤nlen[i],∑i=1nlen[i]+n−1]\displaystyle [\max_{1 \leq i \leq n}{len[i]}, \sum_{i = 1}^n len[i] + n - 1] （注意空格也占据一个字符宽度）, 其中 len[i]len[i] 表示第 ii 个字符串的长度，故可以得到行宽范围区间最大长度近似为 2500×80=2×1052500 \times 80 = 2 \times 10^5, 故可以判断出，对于每一个行宽，判断最长川流长度的算法的时间复杂度是 O(n)\mathrm{O}(n) 且需要常数较小。
首先，很容易在 O(n)\mathrm{O}(n) 的时间复杂度下计算出每个空格在行中的位置（根据题目要求，一行的最后是没有空格的）。通过不断往某一行中加字符串，如果不能加就换行。如果加了某个字符串后还能再加一个字符串，则紧跟着该字符串的空格可以被记录。
得到每一行的空格的位置后，我们设 cnt[i][j]cnt[i][j] 表示 第 1∼i1 \sim i 行中，以第 ii 行，位置为 jj 的空格结尾的最长川流长度，G[i][j]G[i][j] 表示第 ii 行的第 jj 个位置是否为符合条件的空格（是，则值为 11；否则为 00）。
则可以得到如下转移表达式：
cnt[i][j]=max⁡{cnt[i−1][j−1]+1if G[i−1][j−1]cnt[i−1][j]+1if G[i−1][j]cnt[i−1][j+1]+1if G[i−1][j+1]1elsecnt[i][j] = \max \begin{cases} cnt[i - 1][j - 1] + 1 & if \ G[i - 1][j - 1] \\ cnt[i - 1][j] + 1 & if\ G[i - 1][j] \\ cnt[i - 1][j + 1] + 1 & if \ G[i - 1][j + 1] \\ 1 & else \end{cases}
答案即为 max⁡{cnt[i][j]}\max\{cnt[i][j]\}.
但是这样开 cntcnt 数组是开不下的，故我们考虑直接删去第一维（由于两个符合条件的空格之间的距离至少为 22, 故 cnt[j]cnt[j] 从 cnt[j−1]cnt[j - 1] 转移时不会受到同行空格的影响）。
同样，GG 数组也是开不下的，但是如果使用滚动数组，每次将 所有 jj 的状态都赋值过去的话，常数会达到 8080, 从而导致无法通过。
故我们只用赋值两行中存有空格的 jj。用 a,ba, b 两个数组分别记录第 i−1i - 1 和 ii 行所有空格的位置。当 cntcnt 数组处理完第 ii 行后，将 aa 数组内所有元素的标记去除，并将 bb 数组内的所有元素打上标记。
考虑到行宽在变化时 cntcnt 数组需要清零但也不能每次将数组内的元素均清零，故用一个数组记录每个行宽下所有空格在对应行中的位置，然后只将这些位置的 cntcnt 清零即可。
代码如下：
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100;
const int MAXM = 3000;
char str[MAXN];
int n, len[MAXM], sum, maxx, cnt[MAXN * MAXM], ans, ansx, aa[MAXM], bb[MAXM];
int G[MAXM]; 
bool used[MAXN * MAXM];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> str + 1;
		len[i] = strlen(str + 1);
		maxx = max(maxx, len[i]); 
		sum += len[i];
	}	
	for (int gap = maxx; gap < sum + n; gap++) {
		int maxx = 0;
		int j = 1, Len = 0, eid1 = 0, eid = 0;
		int len1 = 0, len2 = 0;
		while (j <= n) {
			++eid1;
			while (Len + len[j] <= gap && j <= n) {
				Len = Len + len[j] + 1;
				if (Len + len[j + 1] <= gap && j < n) {
					G[++eid] = Len;
					bb[++len2] = Len;
					int A = 0;
					if (used[Len - 1]) A = max(A, cnt[Len - 1]);
					if (used[Len]) A = max(A, cnt[Len]); 
					if (used[Len + 1]) A = max(A, cnt[Len + 1]);
					cnt[Len] = A + 1;
					maxx = max(maxx, cnt[Len]);
				}
				j++;
			}
			Len = 0;
			for (int i = 1; i <= len1; i++) used[aa[i]] = false;
			for (int i = 1; i <= len2; i++) used[bb[i]] = true;
			len1 = len2;
			for (int i = 1; i <= len2; i++) aa[i] = bb[i];
			len2 = 0;
		}
		for (int i = 1; i <= len1; i++) used[aa[i]] = false;
		for (int i = 1; i <= eid; i++) cnt[G[i]] = 0;
		if (maxx > ans) {
			ans = maxx;
			ansx = gap;
		}
	}
	cout << ansx << " " << ans << endl;
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...