这名字听起来实在有点耳熟。。？
好吧去年暑假就应该过的题。。。切了
先注意到，天使施魔法的次数不限；我们可以使得某个时刻在特定方向移动一段距离（最长的长度为那个时间段）然后怎么来考虑这个DP；
T，X，Y三维状态很好想到，刚开始的时刻是1，T-1的方向已知，要么从那个方向移动到X，Y，要么在此位置不动。现在来优化这个DP。我们的动机是把O(N*M*T)->O(N*M*K),至于为什么要这要做。。。（题感啊题感,所有的优化都是优化转移嘛不可能优化状态了，所以当转移都无法优化的时候我们只能考虑来改变这个状态。K是时间段的个数，可以想到，其实在同一时间段里面，操作几乎都是相同的。那么dp[K][X][Y]表示在K这段时间内，位于（X，Y）这个位置，从时段1到时段K的最大位移。那么转移就成为了：dp[K][X][Y]=MAX{dp[K-1][X'][Y']+DIST}
*举个例子，假如当前时间段朝向是往右，那么dp[k][x][y]=max{dp[k-1][x][y-Δy]+Δy}=y+max{dp[k-1][x][y']-y'},Δy自然要小于等于当前时间段的长度。现在转移就可以被优化了，我们把k-1时间段的状态记载下来，保证单调递减就OK了，其它三个方向也是类似的：
left：dp[k][x][y]=max{dp[k-1][x][y']+y'}-y
up：dp[k][x][y]=max(dp[k-1][x'][y]+x'}-x
down:dp[k][x][y]=max(dp[k-1][x'][y]-x'}+x
在执行队列的过程中我们有几个需要维护的地方，如果当前自己是家具，那么没关系，我们清空队列；
如果要放进的那个是不合法的，那就不放。
CODE:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300
using namespace std;
int n,m,x0,y0,k,ans;
][][];
];
int main()
{
];
scanf("%d%d%d%d%d",&n,&m,&x0,&y0,&k);
;i<=n;i++)
{
scanf("%s",s);
;j<=m;j++)
]==;
}
;i<=k;i++)scanf("%d%d%d",&st[i],&ed[i],&ff[i]);
memset(dp,-,sizeof(dp));
dp[][x0][y0]=;
;i<=k;i++)
{
);
){//向右
;xx<=n;xx++)
{
,tail=;q[].x=dp[i-][xx][]-;q[].h=;
][xx][]==-)tail--;
;yy<=m;yy++)
{
while(tou<=tail&&(yy-q[tou].h>len))tou++;
)if(tou<=tail)dp[i][xx][yy]=q[tou].x+yy;
//if(dp[i][xx][yy]>-1)printf("you===%d %d %d %d %d\n",i,xx,yy,dp[i][xx][yy],q[tou].h);
){tail=tou-;}
][xx][yy+]==-)continue;
][xx][yy+]-yy->q[tail].x)tail--;
tail++;q[tail].x=dp[i-][xx][yy+]-yy-;q[tail].h=yy+;
}
}
}
)//left
{
;xx<=n;xx++)
{
,tail=;q[].x=dp[i-][xx][m]+m;q[].h=m;
][xx][m]==-)tail--;
;yy--)
{
while(tou<=tail&&q[tou].h-yy>len)tou++;
)if(tou<=tail)dp[i][xx][yy]=q[tou].x-yy;
//if(dp[i][xx][yy]>-1)printf("zuo===%d %d %d %d %d\n",i,xx,yy,dp[i][xx][yy],q[tou].h);
)tail=tou-;
][xx][yy-]==-)continue;
][xx][yy-]+yy->q[tail].x)tail--;
tail++;q[tail].x=dp[i-][xx][yy-]+yy-;q[tail].h=yy-;
}
}
}
)//向上
{
;yy<=m;yy++)
{
,tail=;q[].x=dp[i-][n][yy]+n;q[].h=n;
][n][yy]==-)tail--;
;xx--)
{
while(tou<=tail&&q[tou].h-xx>len)tou++;
)if(tou<=tail)dp[i][xx][yy]=q[tou].x-xx;
//if(dp[i][xx][yy]>-1)printf("up===%d %d %d %d %d\n",i,xx,yy,dp[i][xx][yy],q[tou].h);
)tail=tou-;
][xx-][yy]==-)continue;
][xx-][yy]+xx->q[tail].x)tail--;
tail++;q[tail].x=dp[i-][xx-][yy]+xx-;q[tail].h=xx-;
}
}
}
)//xia
{
;yy<=m;yy++)//down
{
,tail=;q[].x=dp[i-][][yy]-;q[].h=;
][][yy]==-)tail--;
;xx<=n;xx++)
{
while(tou<=tail&&xx-q[tou].h>len)tou++;
)if(tou<=tail)dp[i][xx][yy]=q[tou].x+xx;
//if(dp[i][xx][yy]>-1)printf("xia===%d %d %d %d %d\n",i,xx,yy,dp[i][xx][yy],q[tou].h);
)tail=tou-;
][xx+][yy]==-)continue;
][xx+][yy]-xx->q[tail].x)tail--;
tail++;q[tail].x=dp[i-][xx+][yy]-xx-;q[tail].h=xx+;
}
}
}
}
;i<=n;i++)
;j<=m;j++)
if(dp[k][i][j]>ans)ans=dp[k][i][j];
//printf("%d %d %d\n",i,j,dp[k][i][j]);
printf("%d",ans);
}