洛谷 P2254 [NOI2005] 瑰丽华尔兹

题目来源于：洛谷

题目本质：动态规划，单调队列

解题思路：

f[i][x][y] = max(f[i - 1][x’][y']) + dist(x,y,x',y');

i表示的是第i个时间段结束后，(x,y)这个位置最长的滑行距离。

注意(x,y)与(x',y')必定是在同一列或同一行上的，但不一定相邻。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, k, s1, t1, d1;
int  f[210][210][210];
int ans, dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1}, q[100010], pos[100010], head, tail; 
char a[310][310];
void push(int now, int val, int x, int y){if (val == -0x7f7f7f7f){return;}while (head <= tail && val - now >= q[tail]){tail--;}q[++tail] = val - now;pos[tail] = now;
}
void dp(int p, int x, int y, int d, int t){	if (t < 1){return;}head = 1; tail = 0; int now = 1;while(x <= n && x > 0 && y <= m && y > 0){if (a[x][y] == 'x') head = 1, tail = 0;else push(now, f[p - 1][x][y], x, y);while(head <= tail && now - pos[head] > t) head++;if (head <= tail) f[p][x][y] = q[head] + now;else f[p][x][y] = -0x7f7f7f7f;ans = max(ans, f[p][x][y]); x += dx[d];y += dy[d];now++;}
}int main(){cin >> n >> m >> x >> y >> k;memset(f, 128, sizeof(f));for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)f[0][i][j] = -0x7f7f7f7f;f[0][x][y] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= k; i++){cin >> s1 >> t1 >> d1;if (d1 == 1) {for (int j = 1; j <= m; j++)dp(i, n, j, d1, t1 - s1 + 1);}if (d1 == 2) {for (int j = 1; j <= m; j++)dp(i, 1, j, d1, t1 - s1 + 1);}if (d1 == 3) {for (int j = 1; j <= n; j++)dp(i, j, m, d1, t1 - s1 + 1);}if (d1 == 4) {for (int j = 1; j <= n; j++)dp(i, j, 1, d1, t1 - s1 + 1);}}cout << ans << endl;return 0;
}