[ABC265F] Manhattan Cafe 题解

思路解析

很有思维难度的一道题。思路是dp，\(f[i][j][k]\) 表示已经计算了 \(i\) 维，距离点 \(p\) 的距离为 \(j\) ，距离点 \(q\) 的距离为 \(k\) 时的整点 \(r\) 个数，由此可见我们的每一维都可以从上一维推出来，也即 \(f[i][j][k]\) 可以由 \(f[i-1][j-\Delta j][k-\Delta k]\) 推出，这里的 \(\Delta\) 是指对于每一个 \(r\) ，它和 \(p\) 和 \(q\) 在当前这一维上所需要增加的值，具体内容可以参考这张图：

由此图可见我们需要分类讨论在这一维上 \(r\) 和 \(p\) 和 \(q\) 之间的位置关系，其过程如下：

• 这里的 \(s\) 代表的是 \(\left|p[i]-q[i]\right|\)，也就是 \(p[i]\) 和 \(q[i]\) 之间的区间长度。

如果你能想到这一步，非常好，你已经获得了一个 \(O(nd^3)\) 的程序，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll N = 110, D = 1010, mod = 998244353;
ll n, d;
ll p[N], q[N];
ll f[N][2 * D][D], sum[2 * D][D], sum2[2 * D][D];
int main() {
	cin >> n >> d;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> q[i];
	}
	f[0][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		ll s = abs(p[i] - q[i]);
		for(int j = 0; j <= 2 * d; j++) {
			for(int k = 0; k <= d; k++) {
				f[i][j][k] = 0;
				for(int l = 0; l <= s; l++) {
					if(j - l >= 0 && k - s + l >= 0) {
						f[i][j][k] += f[i - 1][j - l][k - s + l];
						f[i][j][k] %= mod;
					}
				}
				for(int l = 1; j - l >= 0 && k - s - l >= 0; l++) {
					if(j - l >= 0 && k - s - l >= 0) {
						f[i][j][k] += f[i - 1][j - l][k - s - l];
						f[i][j][k] %= mod;
					}
				}
				for(int l = 1; j - s - l >= 0 && k - l >= 0; l++) {
					if(j - s - l >= 0 && k - l >= 0) {
						f[i][j][k] += f[i - 1][j - s - l][k - l];
						f[i][j][k] %= mod;
					}
				}
			}
		}
	}
	ll ans = 0;
	for(ll j = 0; j <= d; j++) {
		for(ll k = 0; k <= d; k++) {
			if(abs(j - k) <= d) {
				ans += f[n][j][k];
				ans %= mod;
			}
		}
	}
	cout << ans;
	return 0;
}

但很遗憾此题数据为 \(n \leq 100, d \leq 1000\) 无法通过。可是我们发现每一次的 \(f[i][j][k]\) 的累加都是成对角线形状累加的，于是便可想到使用前缀和进行优化：

• 对于第一种情况：可见这种情况的对角线是一条垂直于主对角线的对角线，可以用一个 \(sum[j][k]\) 表示 \(j, k\) 所存在的这条对角线从 \(f[i-1][0][k+1]\) 一直累加到 \(f[i-1][j][k]\) 的值。但是需要注意我们只选取对角线中结尾为 \(j, k\) 且长度最长为 \(s\) ，因为只有这些情况的取值是符合这种情况分类讨论的判断条件的。以及如果对角线的两端小于 \(0\) ，也就是两端不存在，我们就特判两端是否存在，只统计剩余的存在的部分（我就是因为这里卡了一晚上。

• 对于第二和第三种情况：可见它们所经过的对角线是一条平行于主对角线的对角线，可以用一个 \(sum2[j][k]\) 表示从这条对角线的开头累加到 \(f[i-1][j][k]\) 的值。

具体内容见下图：

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll N = 110, D = 1010, mod = 998244353;
ll n, d;
ll p[N], q[N];
ll f[N][2 * D][D], sum[2 * D][2 * D], sum2[2 * D][2 * D];
int main() {
	cin >> n >> d;
	for(ll i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for(ll i = 1; i <= n; i++) {
		cin >> q[i];
	}
	f[0][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		memset(sum, 0, sizeof(sum));	//别忘了清空数组
		memset(sum2, 0, sizeof(sum2));
		for(ll j = 0; j <= d; j++) {
			for(ll k = 0; k <= d; k++) {
				if(j - 1 >= 0) {
					sum[j][k] += sum[j - 1][k + 1];
					sum[j][k] %= mod;	//记得取模
				}
				sum[j][k] += f[i - 1][j][k];
				sum[j][k] %= mod;
				if(j - 1 >= 0 && k - 1 >= 0) {
					sum2[j][k] += sum2[j - 1][k - 1];
					sum2[j][k] %= mod;
				}
				sum2[j][k] += f[i - 1][j][k];
				sum2[k][k] %= mod;
			}
		}
		ll s = abs(p[i] - q[i]);
		for(ll j = 0; j <= d; j++) {
			for(ll k = 0; k <= d; k++) {
				f[i][j][k] = 0;
				if(k - s >= 0) {	//细节特判
					if(j - s >= 0) {
						f[i][j][k] += (sum[j][k - s] - sum[j - s][k] + f[i - 1][j - s][k]) % mod;
					}
					else {
						f[i][j][k] += (sum[j][k - s] - sum[0][k - s + j] + f[i - 1][0][k - s + j]) % mod;
					}
				}
				else {
					if(j - s >= 0) {
						f[i][j][k] += (sum[j - s + k][0] - sum[j - s][k] + f[i - 1][j - s][k]) % mod;
					}
					else {
						f[i][j][k] += (sum[j - s + k][0] - sum[0][k - s + j] + f[i - 1][0][k - s + j]) % mod;
					}
				}
				f[i][j][k] %= mod;
				if(j - 1 >= 0 && k - s - 1 >= 0) {
					f[i][j][k] += sum2[j - 1][k - s - 1];
					f[i][j][k] %= mod;
				}
				if(j - s - 1 >= 0 && k - 1 >= 0) {
					f[i][j][k] += sum2[j - s - 1][k - 1];
					f[i][j][k] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(ll j = 0; j <= d; j++) {
		for(ll k = 0; k <= d; k++) {
			ans += f[n][j][k];
			ans %= mod;
		}
	}
	cout << ans;
	return 0;
}