測(cè)試地址：瑰麗華爾茲

做法：設(shè)f(i,x,y)為第i段時(shí)間之后鋼琴正好滑動(dòng)到第x行第y列的最長(zhǎng)滑動(dòng)距離，很容易想到狀態(tài)轉(zhuǎn)移方程，按照傾斜方向分為四種情況考慮，這里只列出傾斜方向?yàn)?（向上）的情況：f(i,x,y)=max(f(i-1,x+s,y)+s)，其中s≤鋼琴與當(dāng)前傾斜方向的反方向上最近的障礙物或者船的邊緣的距離（看上去很繞對(duì)不對(duì)...其實(shí)s就相當(dāng)于鋼琴在這一個(gè)時(shí)間段內(nèi)滑動(dòng)的距離），如果死算時(shí)間復(fù)雜度將是O(n^3*k)，難以接受，考慮單調(diào)隊(duì)列優(yōu)化。

還是討論傾斜方向?yàn)?的情況。先將狀態(tài)轉(zhuǎn)移方程變形為f(i,x,y)=max(f(i-1,x+s,y)+(x+s))-x，令k=x+s，則f(i,x,y)=max(f(i-1,k,y)+k)-x，注意到k的取值范圍是單調(diào)遞增的，且f(i-1,k,y)+k為由k可在O(1)時(shí)間內(nèi)確定的常數(shù)，滿(mǎn)足單調(diào)隊(duì)列優(yōu)化的性質(zhì)，因此可以將時(shí)間復(fù)雜度降低一維，變成O(n^2*k)，這樣就可以接受了。對(duì)于其他傾斜方向，用類(lèi)似的方法進(jìn)行分析就可以了。

以下是本人代碼：

#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#define inf 999999999using namespace std;int n,m,x,y,t,f[2][210][210],que[210];char g[210][210];int main(){  scanf("%d%d%d%d%d",&n,&m,&x,&y,&t);  for(int i=1;i<=n;i++)  {    getchar();	for(int j=1;j<=m;j++)	  scanf("%c",&g[i][j]);  }    int now=0,past=1;  for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)	  if (i==x&&j==y) f[past][i][j]=0;	  else f[past][i][j]=-inf;  for(int i=1,a,b,c;i<=t;i++)  {    scanf("%d%d%d",&a,&b,&c);	int ti=b-a+1,h,t;	switch(c)	{	  case 1:{	           for(int j=1;j<=m;j++)			   {			     h=1,t=0;				 for(int k=n;k>=1;k--)				 {				   if (g[k][j]=='x') h=t+2;				   else				   {				     while(h<=t&&que[h]>k+ti) h++;					 while(h<=t&&f[past][k][j]+k>f[past][que[t]][j]+que[t]) t--;				   }				   que[++t]=k;				   if (h<=t) f[now][k][j]=f[past][que[h]][j]+que[h]-k;				   else f[now][k][j]=-inf;				 }			   }			   break;	         }	  case 2:{	           for(int j=1;j<=m;j++)			   {			     h=1,t=0;				 for(int k=1;k<=n;k++)				 {				   if (g[k][j]=='x') h=t+2;				   else				   {				     while(h<=t&&que[h]<k-ti) h++;					 while(h<=t&&f[past][k][j]-k>f[past][que[t]][j]-que[t]) t--;				   }				   que[++t]=k;				   if (h<=t) f[now][k][j]=f[past][que[h]][j]-que[h]+k;				   else f[now][k][j]=-inf;				 }			   }			   break;	         }	  case 3:{	           for(int j=1;j<=n;j++)			   {			     h=1,t=0;				 for(int k=m;k>=1;k--)				 {				   if (g[j][k]=='x') h=t+2;				   else				   {				     while(h<=t&&que[h]>k+ti) h++;					 while(h<=t&&f[past][j][k]+k>f[past][j][que[t]]+que[t]) t--;				   }				   que[++t]=k;				   if (h<=t) f[now][j][k]=f[past][j][que[h]]+que[h]-k;				   else f[now][j][k]=-inf;				 }			   }			   break;	         }	  case 4:{	           for(int j=1;j<=n;j++)			   {			     h=1,t=0;				 for(int k=1;k<=m;k++)				 {				   if (g[j][k]=='x') h=t+2;				   else				   {				     while(h<=t&&que[h]<k-ti) h++;					 while(h<=t&&f[past][j][k]-k>f[past][j][que[t]]-que[t]) t--;				   }				   que[++t]=k;				   if (h<=t) f[now][j][k]=f[past][j][que[h]]-que[h]+k;				   else f[now][j][k]=-inf;				 }			   }			   break;	         }	}	swap(now,past);  }    int ans=0;  for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)	  ans=max(ans,f[past][i][j]);    PRintf("%d",ans);    return 0;}