这名字听起来实在有点耳熟。。?
好吧去年暑假就应该过的题。。。切了
先注意到,天使施魔法的次数不限;我们可以使得某个时刻在特定方向移动一段距离(最长的长度为那个时间段)然后怎么来考虑这个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); }