【NOI2005T1】瑰丽华尔兹-DP单调队列优化

测试地址：瑰丽华尔兹

做法：设f(i,x,y)为第i段时间之后钢琴正好滑动到第x行第y列的最长滑动距离，很容易想到状态转移方程，按照倾斜方向分为四种情况考虑，这里只列出倾斜方向为1（向上）的情况：f(i,x,y)=max(f(i-1,x+s,y)+s)，其中s≤钢琴与当前倾斜方向的反方向上最近的障碍物或者船的边缘的距离（看上去很绕对不对...其实s就相当于钢琴在这一个时间段内滑动的距离），如果死算时间复杂度将是O(n^3*k)，难以接受，考虑单调队列优化。

还是讨论倾斜方向为1的情况。先将状态转移方程变形为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的取值范围是单调递增的，且f(i-1,k,y)+k为由k可在O(1)时间内确定的常数，满足单调队列优化的性质，因此可以将时间复杂度降低一维，变成O(n^2*k)，这样就可以接受了。对于其他倾斜方向，用类似的方法进行分析就可以了。

以下是本人代码：

#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;}