P2254 [NOI2005] 瑰丽华尔兹 题解

注意到可以设朴素转移方程 \(f_{t,i,j}\) 表示 \(t\) 时刻钢琴在 \((i,j)\) 时的最长滑动距离，这样复杂度是 \(O(nmt)\) 的，过不去。不过听说加点奇怪的优化能过？

考虑一段时刻内钢琴的移动方向是连续的，于是可以改一改状态，\(f_{p,i,j}\) 表示第 \(p\) 段时间结束后钢琴在 \((i,j)\) 时的最长滑动距离。接下来以向右滑动为例子。

注意到可以写出转移方程：

然后这是一个单调队列优化的形式，这样总复杂度就是 \(O(nmk)\) 的，四个方向都这样搞一下就好了。

Code：

/*
========= Plozia =========
	Author:Plozia
	Problem:P2254 [NOI2005] 瑰丽华尔兹
	Date:2022/11/11
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;
using std::deque;

const int MAXN = 200 + 5, INF = 0x3f3f3f3f;
int n, m, Start, End, k, f[2][MAXN][MAXN];
char ch[MAXN][MAXN];
struct node { int l, r, d; bool operator <(const node &fir)const { return l < fir.l; } } a[MAXN];

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}

int main()
{
	n = Read(), m = Read(), Start = Read(), End = Read(), k = Read();
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) std::cin >> ch[i][j];
	for (int i = 1; i <= k; ++i) a[i].l = Read(), a[i].r = Read(), a[i].d = Read();
	int now = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) f[now][i][j] = -INF;
	std::sort(a + 1, a + k + 1); f[now][Start][End] = 0;
	for (int _ = 1; _ <= k; ++_)
	{
		now ^= 1; int len = a[_].r - a[_].l + 1;
		for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) f[now][i][j] = -INF;
		if (a[_].d == 1) // f[i][j] = f[k][j] + k - i
		{
			for (int j = 1; j <= m; ++j)
			{
				deque <int> q;
				for (int i = n; i >= 1; --i)
				{
					while (!q.empty() && q.front() - i > len) q.pop_front();
					if (ch[i][j] == 'x') q.clear();
					else
					{
						while (!q.empty() && f[now ^ 1][q.back()][j] + q.back() <= f[now ^ 1][i][j] + i) q.pop_back();
						q.push_back(i); f[now][i][j] = f[now ^ 1][q.front()][j] + q.front() - i;
					}
				}
			}
		}
		else if (a[_].d == 2) // f[i][j] = f[k][j] + i - k
		{
			for (int j = 1; j <= m; ++j)
			{
				deque <int> q;
				for (int i = 1; i <= n; ++i)
				{
					while (!q.empty() && i - q.front() > len) q.pop_front();
					if (ch[i][j] == 'x') q.clear();
					else
					{
						while (!q.empty() && f[now ^ 1][q.back()][j] - q.back() <= f[now ^ 1][i][j] - i) q.pop_back();
						q.push_back(i); f[now][i][j] = f[now ^ 1][q.front()][j] + i - q.front();
					}
				}
			}
		}
		else if (a[_].d == 3) // f[i][j] = f[i][k] + k - j
		{
			for (int i = 1; i <= n; ++i)
			{
				deque <int> q;
				for (int j = m; j >= 1; --j)
				{
					while (!q.empty() && q.front() - j > len) q.pop_front();
					if (ch[i][j] == 'x') q.clear();
					else
					{
						while (!q.empty() && f[now ^ 1][i][q.back()] + q.back() <= f[now ^ 1][i][j] + j) q.pop_back();
						q.push_back(j); f[now][i][j] = f[now ^ 1][i][q.front()] + q.front() - j;
					}
				}
			}
		}
		else // f[i][j] = f[i][k] + j - k
		{
			for (int i = 1; i <= n; ++i)
			{
				deque <int> q;
				for (int j = 1; j <= m; ++j)
				{
					while (!q.empty() && j - q.front() > len) q.pop_front();
					if (ch[i][j] == 'x') q.clear();
					else
					{
						while (!q.empty() && f[now ^ 1][i][q.back()] - q.back() <= f[now ^ 1][i][j] - j) q.pop_back();
						q.push_back(j); f[now][i][j] = f[now ^ 1][i][q.front()] + j - q.front();
					}
				}
			}
		}
	}
	int ans = -INF;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans = std::max(ans, f[now][i][j]);
	printf("%d\n", ans); return 0;
}

原文地址：http://www.cnblogs.com/Plozia/p/16880325.html