P2254 [NOI2005]瑰丽华尔兹
不妨认为舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。
艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。
输入输出格式
输入格式：
输入文件的第一行包含5个数N, M, x, y和K。N和M描述舞厅的大小，x和y为钢琴的初始位置；我们对船体倾斜情况是按时间的区间来描述的，且从1开始计算时间，比如“在[1, 3]时间里向东倾斜，[4, 5]时间里向北倾斜”，因此这里的K表示区间的数目。
以下N行，每行M个字符，描述舞厅里的家具。第i 行第j 列的字符若为‘ . ’，则表示该位置是空地；若为‘ x ’，则表示有家具。
以下K行，顺序描述K个时间区间，格式为：si ti di(1 ≤ i ≤ K)。表示在时间区间[si, ti]内，船体都是向di方向倾斜的。di为1, 2, 3, 4中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即
s1 = 1 ti = si-1 + 1 (1 < i ≤ K)
tK = T
输出格式：
输出文件仅有1行，包含一个整数，表示钢琴滑行的最长距离(即格子数)。
（解释会发在代码里QAQ
（这题我就是给洛谷题解加一个解释 这样以后方便罢了
#include<cstdio> #include<cstring> #include<iostream> #define MAXN 205 using namespace std; int n, m, sx, sy, K, ans, dp[MAXN][MAXN]; int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1}; struct node{int dp, pos;}q[MAXN]; //q为单调递减队列，要存位置信息用来计算共走了几步 char map[MAXN][MAXN]; void work(int x, int y, int len, int d) //第k个区间的时长为len，方向为d，起点坐标x,y { int head = 1, tail = 0; for(int i = 1; x >= 1 && x <= n && y >= 1 && y <= m; i++, x += dx[d], y += dy[d])//判断是否可以循环 if(map[x][y] == 'x') head = 1, tail = 0; //遇到障碍，清空队列 else { while(head <= tail && q[tail].dp + i - q[tail].pos < dp[x][y]) tail--;//如果当前移动距离小于记录距离 q[++tail] = node{dp[x][y], i}; //当前值入队列 if(q[tail].pos - q[head].pos > len) head++; //队列长度超过len时队首弹出 dp[x][y] = q[head].dp + i - q[head].pos; //最优解是队首元素+移动距离 ans = max(ans, dp[x][y]); //记录结果 } } int main() { scanf("%d%d%d%d%d", &n, &m, &sx, &sy, &K); for(int i = 1; i <= n; i++) scanf("%s", map[i] + 1); memset(dp, 0xf3, sizeof(dp)); dp[sx][sy] = 0; //初始化，只有初始位置是0，其他都是负无穷 for(int k = 1, s, t, d, len; k <= K; k++) { scanf("%d%d%d", &s, &t, &d); len = t - s + 1; if(d == 1) for(int i = 1; i <= m; i++) work(n, i, len, d);//因为是向上走 所以要从后向前走 if(d == 2) for(int i = 1; i <= m; i++) work(1, i, len, d);//其他也一样 if(d == 3) for(int i = 1; i <= n; i++) work(i, m, len, d); if(d == 4) for(int i = 1; i <= n; i++) work(i, 1, len, d); } printf("%d", ans); return 0; }
f(i,x,y)f(i,x,y)表示第i个区间（区间长设为L）后，钢琴处于(x,y)(x,y)的最大滑行距离
假如这个区间方向是向下，则f(i−1,j,y)+(x−j)−>f(i,x,y)(x−L<=j<=x)f(i−1,j,y)+(x−j)−>f(i,x,y)(x−L<=j<=x)
即这个区间的转移是一列一列的，每一列用一下单调队列优化dp即可
悄悄拿来hzwer的解答qwqqqqq
优质内容筛选与推荐>>1、IE8 兼容性解决--1
2、欧洲杯观战日记：奥地利队真的排名比中国队靠后么？
3、北京发出抑制私家车“信号” 养车成本越来越高
4、我设想的接口
5、Hive中的数据倾斜