简单dp，设$f_{i,j,k}$表示第i个时间段，钢琴处在（j,k）位置移动距离的最大值,那么有转移
$f_{i, j, k} = max(f_{i - 1, j, k}) , f_{i, j, k} = max(f_{i - 1, a, b})$
其中
$j - dx_{d_{i}} * lenleq a leq j -1 $
$k - dy_{d_{i}} * lenleq b leq k -1 $
$len = ed_{i} - st_{i} + 1 $
其实就是一个滑动窗口，考虑到转移顺序，就是写四遍单调队列~
但是我成功地把方程写错了…… i - 1 写成了 i ，改掉就A了
Code：
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int N = 205; int n, m, segNum, st[N], ed[N], d[N]; int fx, fy, f[N][N][N], q[N]; char mp[N][N]; inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline void chkMax(int &x, int y) { if(y > x) x = y; } inline void print(int p) { printf(" %d ", p); for(int i = 1; i <= n; i++, printf(" ")) for(int j = 1; j <= m; j++) printf("%10d ", f[p][i][j]); system("pause"); } int main() { read(n), read(m), read(fx), read(fy), read(segNum); for(int i = 1; i <= n; i++) scanf("%s", mp[i] + 1); for(int i = 1; i <= segNum; i++) read(st[i]), read(ed[i]), read(d[i]); memset(f, 0xcf, sizeof(f)); f[0][fx][fy] = 0; for(int i = 1; i <= segNum; i++) { for(int j = 1; j <= n; j++) for(int k = 1; k <= m; k++) if(mp[j][k] != 'x') chkMax(f[i][j][k], f[i - 1][j][k]); // print(i); int len = ed[i] - st[i] + 1; if(d[i] == 1) { for(int k = 1; k <= m; k++) { int l = 1, r = 0; for(int j = n; j >= 1; j--) { for(; l <= r && q[l] > j + len; l++); if(mp[j][k] == 'x') l = 1, r = 0; else if(l <= r) chkMax(f[i][j][k], f[i - 1][q[l]][k] + (q[l] - j)); if(f[i - 1][j][k] >= 0) { for(; l <= r && f[i - 1][q[r]][k] + (q[r] - j) < f[i - 1][j][k]; r--); q[++r] = j; } } } } if(d[i] == 2) { for(int k = 1; k <= m; k++) { int l = 1, r = 0; for(int j = 1; j <= n; j++) { for(; l <= r && q[l] < j - len; l++); if(mp[j][k] == 'x') l = 1, r = 0; else if(l <= r) chkMax(f[i][j][k], f[i - 1][q[l]][k] + (j - q[l])); if(f[i - 1][j][k] >= 0) { for(; l <= r && f[i - 1][q[r]][k] + (j - q[r]) < f[i - 1][j][k]; r--); q[++r] = j; } } } } if(d[i] == 3) { for(int j = 1; j <= n; j++) { int l = 1, r = 0; for(int k = m; k >= 1; k--) { for(; l <= r && q[l] > k + len; l++); if(mp[j][k] == 'x') l = 1, r = 0; else if(l <= r) chkMax(f[i][j][k], f[i - 1][j][q[l]] + (q[l] - k)); if(f[i - 1][j][k] >= 0) { for(; l <= r && f[i - 1][j][q[r]] + (q[r] - k) < f[i - 1][j][k]; r--); q[++r] = k; } } } } if(d[i] == 4) { for(int j = 1; j <= n; j++) { int l = 1, r = 0; for(int k = 1; k <= m; k++) { for(; l <= r && q[l] < k - len; l++); if(mp[j][k] == 'x') l = 1, r = 0; else if(l <= r) chkMax(f[i][j][k], f[i - 1][j][q[l]] + (k - q[l])); if(f[i - 1][j][k] >= 0) { for(; l <= r && f[i - 1][j][q[r]] + (k - q[r]) < f[i - 1][j][k]; r--); q[++r] = k; } } } } // print(i); } int ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) chkMax(ans, f[segNum][i][j]); printf("%d ", ans); return 0; }
还是要仔细a