HDU_3620
设f[i][x][y]表示第i个动作结束之后位置在(x,y)的最大步数，那么f[i][x][y]=std::max{f[i-1][x'][y']+distance((x,y),(x',y'))}，然后根据第i个动作的行走方向来遍历数组并进行dp就可以了。但是由于每个动作可以向前行走的最大步数为200，如果再加一维循环表示这个动作走了多少步的话就会超时，不过可以用单调队列优化掉这一维，使得每次的决策都是O(1)的。
此外，每次移动的步数可以是0，也就是不移动。
#include#include #include #define MAXD 210int dx[] = {-1, 0, 1, 0}, dy[] = { 0, -1, 0, 1};char b[MAXD][MAXD];int N, M, K, sx, sy, q[MAXD], f[2][MAXD][MAXD];struct List{ int k, d;}list[MAXD];void init(){ int i; scanf("%d%d%d%d%d", &N, &M, &sx, &sy, &K), -- sx, -- sy; for(i = 0; i < N; i ++) scanf("%s", b[i]); for(i = 0; i < K; i ++) scanf("%d%d", &list[i].k, &list[i].d);}void solve(){ int i, j, k, cur = 0, flag, front, rear, ans = 0; for(i = 0; i < N; i ++) for(j = 0; j < M; j ++) f[0][i][j] = -1; f[0][sx][sy] = 0; for(k = 0; k < K; k ++) { cur ^= 1; if(list[k].d == 1) { for(j = 0; j < M; j ++) { front = rear = 0; for(i = N - 1; i >= 0; i --) { f[cur][i][j] = -1; if(b[i][j] == 'x') { front = rear; continue; } if(f[cur ^ 1][i][j] != -1) { while(front < rear && f[cur ^ 1][i][j] >= f[cur ^ 1][q[rear - 1]][j] + q[rear - 1] - i) -- rear; q[rear ++] = i; } while(front < rear && q[front] - i > list[k].k) ++ front; if(front < rear) f[cur][i][j] = f[cur ^ 1][q[front]][j] + q[front] - i; if(f[cur ^ 1][i][j] == -1) continue; } } } else if(list[k].d == 2) { for(i = 0; i < N; i ++) { front = rear = 0; for(j = M - 1; j >= 0; j --) { f[cur][i][j] = -1; if(b[i][j] == 'x') { front = rear; continue; } if(f[cur ^ 1][i][j] != -1) { while(front < rear && f[cur ^ 1][i][j]>= f[cur ^ 1][i][q[rear - 1]] + q[rear - 1] - j ) -- rear; q[rear ++] = j; } while(front < rear && q[front] - j > list[k].k) ++ front; if(front < rear) f[cur][i][j] = f[cur ^ 1][i][q[front]] + q[front] - j; } } } else if(list[k].d == 3) { for(j = 0; j < M; j ++) { front = rear = 0; for(i = 0; i < N; i ++) { f[cur][i][j] = -1; if(b[i][j] == 'x') { front = rear; continue; } if(f[cur ^ 1][i][j] != -1) { while(front < rear && f[cur ^ 1][i][j] >= f[cur ^ 1][q[rear - 1]][j] + i - q[rear - 1]) -- rear; q[rear ++] = i; } while(front < rear && i - q[front] > list[k].k) ++ front; if(front < rear) f[cur][i][j] = f[cur ^ 1][q[front]][j] + i - q[front]; } } } else { for(i = 0; i < N; i ++) { front = rear = 0; for(j = 0; j < M; j ++) { f[cur][i][j] = -1; if(b[i][j] == 'x') { front = rear; continue; } if(f[cur ^ 1][i][j] != -1) { while(front < rear && f[cur ^ 1][i][j] >= f[cur ^ 1][i][q[rear - 1]] + j - q[rear - 1]) -- rear; q[rear ++] = j; } while(front < rear && j - q[front] > list[k].k) ++ front; if(front < rear) f[cur][i][j] = f[cur ^ 1][i][q[front]] + j - q[front]; } } } } for(i = 0; i < N; i ++) for(j = 0; j < M; j ++) ans = std::max(ans, f[cur][i][j]); printf("%d\n", ans);}int main(){ int t; scanf("%d", &t); while(t --) { init(); solve(); } return 0;}