T1. 廊桥分配

考虑分别求出分配给 " 国内区 " 与 " 国际区 " \(i\) 个廊桥时能停靠的飞机数 \(f_i\) 与 \(g_i\)。
则答案为 \(\max\limits_{0 \leq i \leq n} \{ f_i + g_{n - i} \}\)。

注意到求 \(f, g\) 两个数组的过程是一样的，这里以求 \(f\) 数组为例。

一开始国内区没有廊桥。
考虑将每个飞机的「抵达时间」和「起飞时间」放入一个序列后排序，使用类似扫描线的方法求解：

• 若遇到的是一个飞机的「抵达时间」。

  • 若当前没有可供停靠的廊桥，则新建一个廊桥停靠；
    否则找一个当前没有停靠飞机、且编号最小的廊桥停靠（使用小根堆维护当前可供停靠的廊桥编号）。
  • 然后该将贡献计入该廊桥中。

• 若遇到的是一个飞机的「起飞时间」。则将该飞机停靠的廊桥的编号放入小根堆。

最后对这个贡献数组求一遍前缀和即可求出 \(f\) 数组。

时间复杂度 \(\mathcal{O}(n \log n)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> 

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

const int N = 100100;

int n, m1, m2;

int bel[N];

int len;
struct Node {
	int x, state, id;

	Node() {}
	Node(int A, int B, int C) : x(A), state(B), id(C) {} 
} seq[N * 2];

bool cmp(Node A, Node B) {
	return A.x < B.x;
}

int f[N], g[N];
int num[N];

int cnt;
priority_queue<int> q;

void solve(int m, int f[N]) {
	len = 0, cnt = 0;
	while (q.size()) q.pop(); 
	memset(bel, 0, sizeof(bel));
	memset(num, 0, sizeof(num));

	for (int i = 1; i <= m; i ++) {
		int l = read(), r = read();
		seq[++ len] = (Node) { l, 0, i };
		seq[++ len] = (Node) { r, 1, i };
	}

	sort(seq + 1, seq + 1 + len, cmp);

	for (int i = 1; i <= len; i ++) {
		if (seq[i].state) {
			q.push(-bel[seq[i].id]);
		} else {
			if (q.size()) {
				int id = -q.top(); q.pop();
				bel[seq[i].id] = id;
				num[id] ++;
			} else {
				int id = ++ cnt;
				bel[seq[i].id] = id;
				num[id] ++;
			}
		}
	}

	for (int i = 1; i <= m; i ++) f[i] = f[i - 1] + num[i];
}

int main() {
	n = read(), m1 = read(), m2 = read();

	solve(m1, f);
	solve(m2, g);

	int ans = 0;
	for (int i = 0; i <= n; i ++) {
		int x = i, y = n - i;

		if (x > m1) x = m1;
		if (y < 0) y = 0; if (y > m2) y = m2;

		ans = max(ans, f[x] + g[y]);
	}

	printf("%d\n", ans);

	return 0;
}

T2. 括号序列

显然 dp。线性 dp 不易处理题目中的变换规则，可以考虑区间 dp。

首先可以 \(\mathcal{O}(n^2)\) 预处理一个数组 \(ok(i, j)\) 表示：区间 \([i, j]\) 中的字符串能否表示为不超过 \(k\) 个字符 * 的非空字符串。

然后定义 dp 状态：

• \(f_0(l, r)\)：表示区间 \([l, r]\) 中的字符，能组成多少个符合规范的超级括号序列。
• \(f_1(l, r)\)：表示区间 \([l, r]\) 中的字符，能组成多少个形如 SA 的超级括号序列。
• \(f_2(l, r)\)：表示区间 \([l, r]\) 中的字符，能组成多少个形如 AS 的超级括号序列。
• \(f_3(l, r)\)：表示区间 \([l, r]\) 中的字符，能组成多少个形如 (A) 的超级括号序列。

---

• 对于 \(f_0\) 的转移：
  • 第一种是形如 (...) 的转移。
  • 第二种是形如 AB、ASB 的转移。
    为了做到不重复计数（例如 ABC 可以看成 A + BC 和 AB + C，但是这两种转移本质上是一个方案），我们可以强行认为 AB、ASB 中的 A 是形如 (...) 的串，这样就不会重复计数了。

\[f_0(l, r) = f_1(l, r) + \sum\limits_{l \leq k < r} f_1(l, k) \times \left(f_0(k + 1, r) + f_2(k + 1, r)\right) \]

• 对于 \(f_1\) 的转移：
  • 首先要判断一下 \(s_l\) 是否为字符 ( 或 ? 的其中一个，\(s_r\) 是否为字符 ) 或 ? 的其中一个。
    若不满足，则 \(f_1(l, r) = 0\)。
  • 第一种是形如 (*...*) 的转移。
  • 第二种是形如 (A) 的转移。
  • 第三种是形如 (SA) 的转移。
  • 第四种是形如 (AS) 的转移。

\[f_1(l, r) = [ok(l + 1, r - 1) = 1] + f_0(l + 1, r - 1) + f_2(l + 1, r - 1) + f_3(l + 1, r - 1) \]

• 对于 \(f_2\) 的转移：

\[f_2(l, r) = \sum\limits_{l \leq k < r, ok(l,k) = 1} f_0(k + 1, r) \]

• 对于 \(f_3\) 的转移：

\[f_3(l, r) = \sum\limits_{l < k \leq r, ok(k, r) = 1} f_0(l, k - 1) \]

最后的答案即为 \(f_0(1, n)\)，时间复杂度 \(\mathcal{O}(n^3)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
const int mod = 1e9 + 7;

int n, k;
char s[N];

bool ok[N][N];

bool inc(int i, int j) {
	if (s[i] != '(' && s[i] != '?') return 0;
	if (s[j] != ')' && s[j] != '?') return 0;
	return 1;
}

long long f[4][N][N];

int main() {
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);

	for (int i = 1; i <= n; i ++)
		for (int j = i; j <= n; j ++) {
			if (j - i >= k) break;
			if (s[j] != '*' && s[j] != '?') break;

			ok[i][j] = 1;
		}

	for (int i = 1; i < n; i ++)
		if (inc(i, i + 1)) f[0][i][i + 1] = f[1][i][i + 1] = 1;

	for (int len = 3; len <= n; len ++)
		for (int l = 1; l <= n - len + 1; l ++) {
			int r = l + len - 1;

			// f_1: (...)

			if (inc(l, r)) {
				if (ok[l + 1][r - 1]) f[1][l][r] = 1;
				f[1][l][r] += f[0][l + 1][r - 1];
				f[1][l][r] += f[2][l + 1][r - 1];
				f[1][l][r] += f[3][l + 1][r - 1];
				f[1][l][r] %= mod;
			}

			// f_2: SA

			for (int k = l; k < r; k ++) {
				if (!ok[l][k]) break;
				f[2][l][r] = (f[2][l][r] + f[0][k + 1][r]) % mod;
			}

			// f_3: AS 

			for (int k = r; k > l; k --) {
				if (!ok[k][r]) break;
				f[3][l][r] = (f[3][l][r] + f[0][l][k - 1]) % mod;
			}

			// f_0: all

			f[0][l][r] = f[1][l][r];

			for (int k = l; k < r; k ++)
				f[0][l][r] = (f[0][l][r] + f[1][l][k] * f[0][k + 1][r]) % mod;

			for (int k = l; k < r; k ++)
				f[0][l][r] = (f[0][l][r] + f[1][l][k] * f[2][k + 1][r]) % mod;
		}

	printf("%d\n", f[0][1][n]);

	return 0;
}

T3. 回文

（待填 ...）

T4. 交通规划

（待填 ...）