设f[i][x][y]表示在第i个时段,钢琴在这个时段停止在(x,y)时的最大滑动激励
转移:
dir=1时 f[i][x][y]=max{f[i-1][x+k][y]+k 其中0<=k<=ed-st+1}
dir=2时 f[i][x][y]=max{f[i-1][x-k][y]+k 其中0<=k<=ed-st+1}
dir=3时 f[i][x][y]=max{f[i-1][x][y+k]+k 其中0<=k<=ed-st+1}
dir=4时 f[i][x][y]=max{f[i-1][x][y-k]+k 其中0<=k<=ed-st+1}
优化:
dir=1时优化:f[i][x][y]=max{f[i-1][k][y]+k-x 其中x<=k<=x+ed-st+1} -> 滑动窗口 倒着循环
dir=2时优化:f[i][x][y]=max{f[i-1][k][y]+x-k 其中x-ed+st-1<=k<=x} -> 滑动窗口 顺着循环
dir=3时优化:f[i][x][y]=max{f[i-1][x][k]+k-y 其中y<=k<=y+ed-st+1} -> 滑动窗口 倒着循环
dir=4时优化:f[i][x][y]=max{f[i-1][x][k]+y-k 其中y-ed+st-1<=k<=y} -> 滑动窗口 顺着循环
答案: max{f[k][x][y] 其中1<=x<=n且1<=y<=m}
初始: f[0][start_x][start_y]=0
枚举x(或y)时若是障碍物,则清空队列(因为之前的都没用了)
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <queue>
#include <list>
using namespace std;
const int N = 205;
const int dx[] = {0, -1, 1, 0, 0};
const int dy[] = {0, 0, 0, -1, 1};
int n, m, K, startx, starty;
int st, ed, dir;
char Map[N][N];
int f[N][N][N];
int main() {
scanf("%d%d%d%d%d", &n, &m, &startx, &starty, &K);
for(int i = 1; i <= n; i ++) scanf("%s", Map[i] + 1);
memset(f, -0x3f, sizeof(f));
f[0][startx][starty] = 0;
for(int i = 1; i <= K; i ++) {
scanf("%d%d%d", &st, &ed, &dir);
int len = ed - st + 1;
if(dir == 1) {
for(int y = 1; y <= m; y ++) {
list<int> q;
for(int x = n; x; x --) {
if(Map[x][y] == 'x') { // 障碍物
q.clear(); // 清空
f[i][x][y] = -0x3f3f3f3f;
} else {
while(q.size() && q.front() > x + len) q.pop_front(); // 去掉越界的
while(q.size() && f[i - 1][x][y] > f[i - 1][q.back()][y] + q.back() - x) q.pop_back(); // 去掉不优的
q.push_back(x);
f[i][x][y] = max(f[i][x][y], f[i - 1][q.front()][y] + q.front() - x);
}
}
}
} else if(dir == 2) {
for(int y = 1; y <= m; y ++) {
list<int> q;
for(int x = 1; x <= n; x ++) {
if(Map[x][y] == 'x') {
q.clear();
f[i][x][y] = -0x3f3f3f3f;
} else {
while(q.size() && q.front() < x - len) q.pop_front();
while(q.size() && f[i - 1][x][y] > f[i - 1][q.back()][y] + x - q.back()) q.pop_back();
q.push_back(x);
f[i][x][y] = max(f[i][x][y], f[i - 1][q.front()][y] + x - q.front());
}
}
}
} else if(dir == 3) {
for(int x = 1; x <= n; x ++) {
list<int> q;
for(int y = m; y; y --) {
if(Map[x][y] == 'x') {
q.clear();
f[i][x][y] = -0x3f3f3f3f;
} else {
while(q.size() && q.front() > y + len) q.pop_front();
while(q.size() && f[i - 1][x][y] > f[i - 1][x][q.back()] + q.back() - y) q.pop_back();
q.push_back(y);
f[i][x][y] = max(f[i][x][y], f[i - 1][x][q.front()] + q.front() - y);
}
}
}
} else if(dir == 4) {
for(int x = 1; x <= n; x ++) {
list<int> q;
for(int y = 1; y <= m; y ++) {
if(Map[x][y] == 'x') {
q.clear();
f[i][x][y] = -0x3f3f3f3f;
} else {
while(q.size() && q.front() < y - len) q.pop_front();
while(q.size() && f[i - 1][x][y] > f[i - 1][x][q.back()] + y - q.back()) q.pop_back();
q.push_back(y);
f[i][x][y] = max(f[i][x][y], f[i - 1][x][q.front()] + y - q.front());
}
}
}
}
}
int res = -0x3f3f3f3f;
for(int x = 1; x <= n; x ++)
for(int y = 1; y <= m; y ++)
res = max(res, f[K][x][y]);
printf("%d\n", res);
return 0;
}