http://www.lydsy.com/JudgeOnline/problem.php?id=1499
舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。
艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。
……其实这是单调队列优化吧……
我们有一个显然的f[i][j][k]表示在i时间段内钢琴到(j,k)处时最大移动距离。
显然f可以很简单的转移，但是复杂度会爆炸。
但是又显然可以对每个点单调队列优化……
而且既然不是斜率优化，所以单调队列的维护也很简单，直接看代码吧。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int T=;
const int N=;
inline int read(){
int X=,w=;char ch=;
while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}
while(ch>=''&&ch<='')X=(X<<)+(X<<)+ch-'',ch=getchar();
return X*w;
}
int f[T][N][N],qx[N],qy[N];
char s[N];
bool ok[N][N];
int dx[]={,-,,,};
int dy[]={,,,-,};
struct time{
int t,d;
}p[T];
int n,m;
void dp(int x,int y,int k){
int l=,r=;
while(x>=&&y>=&&x<=n&&y<=m){
while(l<r&&abs(x-qx[l])+abs(y-qy[l])>p[k].t)l++;
while(l<r&&!ok[x][y])r--;
while(l<r){
int t1=f[k-][qx[r-]][qy[r-]]+abs(x-qx[r-])+abs(y-qy[r-]);
int t2=f[k-][x][y];
if(t1<t2)r--;
else break;
}
if(ok[x][y]){
qx[r]=x,qy[r++]=y;
f[k][x][y]=f[k-][qx[l]][qy[l]]+abs(x-qx[l])+abs(y-qy[l]);
}
x+=dx[p[k].d];y+=dy[p[k].d];
}
}
int main(){
n=read(),m=read();
int x=read(),y=read(),t=read();
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=m;j++)ok[i][j]=(s[j]=='.');
}
memset(f,-,sizeof(f));
f[][x][y]=;
for(int i=;i<=t;i++){
int t1=read(),t2=read();
p[i].t=t2-t1+;p[i].d=read();
}
for(int k=;k<=t;k++){
if(p[k].d==)
for(int j=;j<=m;j++)dp(n,j,k);
if(p[k].d==)
for(int j=;j<=m;j++)dp(,j,k);
if(p[k].d==)
for(int i=;i<=n;i++)dp(i,m,k);
if(p[k].d==)
for(int i=;i<=n;i++)dp(i,,k);
}
int ans=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
ans=max(ans,f[t][i][j]);
}
}
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++