526互联

AtCoder Beginner Contest 265 F Manhattan Cafe

发布时间 2023-06-12 22:33:04作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑 dp，\(f_{i, j, k}\) 表示考虑到第 \(i\) 维，\(\sum\limits_{x = 1}^i |p_x - r_x| = j, \sum\limits_{x = 1}^i |q_x - r_x| = k\) 的方案数。转移是容易的，枚举 \(r_i\) 即可，\(f_{i, j, k} = \sum\limits_r f_{i - 1, j - |p_i - r|, k - |q_i - r|}\)。

复杂度 \(O(nD^3)\)，无法接受，考虑下标拆绝对值后前缀和优化。简单讨论一下就行。以 \(p_i \le q_i\) 的情况为例：

  1. \(r_i < p_i\)，\(f_{i, j, k}\) 能从 \(\cdots, f_{i - 1, j - 2, k - q_i + p_i - 2}, f_{i - 1, j - 1, k - q_i + p_i - 1}\) 转移；
  2. \(p_i \le r_i \le q_i\)，\(f_{i, j, k}\) 能从 \(f_{i - 1, j, k - q_i + p_i}, f_{i - 1, j - 1, k - q_i + p_i + 1}, \cdots, f_{i - 1, j - q_i + p_i, k}\) 转移；
  3. \(r_i > q_i\)，\(f_{i, j, k}\) 能从 \(f_{i - 1, j - b_i + a_i - 1, k - 1}, f_{i - 1, j - b_i + a_i - 2, k - 2}, \cdots\) 转移。

也就是说我们只要维护对角线前缀和就好了。

要注意下标越界的问题。对于第 \(1, 3\) 种情况，能转移的是一段前缀或后缀，只要特判下标是否越界即可；对于第 \(2\) 种情况，因为能转移的是一段区间，如果下标为负，就要找到第一个 \(0\) 开始转移。

想清楚了写起来挺快的，不存在难写的问题。注意一些细节问题即可，比如符号写反，或者没取模等等，别像我一样有一处漏了取模然后傻傻调试 20min 就行。

时间复杂度 \(O(nD^2)\)，可以通过。

code 
// Problem: F - Manhattan Cafe
// Contest: AtCoder - AtCoder Beginner Contest 265
// URL: https://atcoder.jp/contests/abc265/tasks/abc265_f
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1010;
const int mod = 998244353;

int n, m, a[maxn], b[maxn], f[2][maxn][maxn], g[3][maxn][maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	f[0][0][0] = 1;
	for (int i = 1, o = 1; i <= n; ++i, o ^= 1) {
		mems(f[o], 0);
		mems(g, 0);
		for (int j = 0; j <= m; ++j) {
			for (int k = 0; k <= m; ++k) {
				g[0][j][k] = f[o ^ 1][j][k];
				if (j && k) {
					g[0][j][k] = (g[0][j][k] + g[0][j - 1][k - 1]) % mod;
				}
			}
		}
		for (int j = m; ~j; --j) {
			for (int k = 0; k <= m; ++k) {
				g[1][j][k] = f[o ^ 1][j][k];
				if (j < m && k) {
					g[1][j][k] = (g[1][j][k] + g[1][j + 1][k - 1]) % mod;
				}
			}
		}
		for (int j = 0; j <= m; ++j) {
			for (int k = m; ~k; --k) {
				g[2][j][k] = f[o ^ 1][j][k];
				if (j && k < m) {
					g[2][j][k] = (g[2][j][k] + g[2][j - 1][k + 1]) % mod;
				}
			}
		}
		for (int j = 0; j <= m; ++j) {
			for (int k = 0; k <= m; ++k) {
				if (a[i] <= b[i]) {
					if (j - 1 >= 0 && k - b[i] + a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - 1][k - b[i] + a[i] - 1]) % mod;
					}
					if (j + 1 <= m && k - b[i] + a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + mod - g[1][j + 1][k - b[i] + a[i] - 1]) % mod;
					}
					int x = j - b[i] + a[i], y = k;
					if (x < 0) {
						y += x;
						x = 0;
					}
					if (y >= 0) {
						f[o][j][k] = (f[o][j][k] + g[1][x][y]) % mod;
					}
					if (j + a[i] - b[i] - 1 >= 0 && k - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j + a[i] - b[i] - 1][k - 1]) % mod;
					}
				} else {
					if (j - a[i] + b[i] - 1 >= 0 && k - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - a[i] + b[i] - 1][k - 1]) % mod;
					}
					if (j - a[i] + b[i] - 1 >= 0 && k + 1 <= m) {
						f[o][j][k] = (f[o][j][k] + mod - g[2][j - a[i] + b[i] - 1][k + 1]) % mod;
					}
					int x = j, y = k - a[i] + b[i];
					if (y < 0) {
						x += y;
						y = 0;
					}
					if (x >= 0) {
						f[o][j][k] = (f[o][j][k] + g[2][x][y]) % mod;
					}
					if (j - 1 >= 0 && k + b[i] - a[i] - 1 >= 0) {
						f[o][j][k] = (f[o][j][k] + g[0][j - 1][k + b[i] - a[i] - 1]) % mod;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j <= m; ++j) {
			ans = (ans + f[n & 1][i][j]) % mod;
		}
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}