**
在这先膜一波\(\cal{rqy}\)，\(rqy\; tql\)！
首先应该能想到正解是\(DP\)。我们可以枚举每个时间点来列出转移方程。
用\(f[i][x][y]\)表示在\(i\)这个时间点走到\((x,y)\)这个位置的最长路径，我们以向下走为例，则：\(dp[i][x][y]=\max(dp[i-1][x][y],dp[i-1][x-1][y]+1)\) 期望得分\(50\)分但不要忘了，题目中的时间是按段给你的，所以我们没有必要去枚举每个时间点，直接枚举时间段就好了。
\(dp[i][x][y]\)表示在第\(i\)个时间点结束时走到了\((x,y)\)这个位置的最长路径，我们还是以向下走为例：\(dp[i][x][y]=\max(dp[i-1][t][y]+x-t)=\max(dp[i][t][y]-t)+x\)，\(len\)表示这次时间段的长度,\(t\in [x-len,x]\)。 这时，我们就可以用单调队列来优化\(max(dp[i][t][y]-t)\)，时间复杂度\(O(nmk)\)#include#include #include #include #define inf 2147483647using namespace std;bool mapp[210][210];int read(){ int k=0,f=1; char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) k=(k<<3)+(k<<1)+c-48; return k*f;}int dp[210][210][210];struct zzz{ int st,pos;}q[100010]; int h,t;int dx[5]={0,-1,1,0,0}, //控制向哪个方向滑动 dy[5]={0,0,0,-1,1};int ans=-inf,n,m;// ==================算法主体==============void f(int tim,int x,int y,int d,int len){ if(len<1) return ; h=1,t=0; int now=1; while(x>0&&x<=n&&y>0&&y<=m){ //判断是否越界 if(mapp[x][y]) h=1,t=0; //如果有障碍,则从之前的状态无法到达 ,清空队列,重新开始 else{ // 入队,成为候选答案 if(dp[tim-1][x][y]!=-inf){ while(h<=t&&dp[tim-1][x][y]-now>=q[t].st) t--; q[++t].st=dp[tim-1][x][y]-now; q[t].pos=now; //记录下标,判断是否超出长度限制 } } while(h<=t&&now-q[h].pos>len) h++; //如果当前的队头超出长度限制 ,则出队 if(h<=t) dp[tim][x][y]=q[h].st+now; // 单调队列,队头即为最大值,直接加上即可 else dp[tim][x][y]=-inf; //无法到达则置为 -inf ans=max(ans,dp[tim][x][y]); //ans记录最大值 x+=dx[d], y+=dy[d]; ++now; //继续滑动 }}//=======================================int main(){ n=read(),m=read(); int sx=read(),sy=read(),num=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(getchar()=='x') mapp[i][j]=1; } getchar(); } memset(dp,128,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[0][i][j]=-inf; dp[0][sx][sy]=0; for(int i=1;i<=num;i++){ int si=read(),ti=read(),dic=read(); if(dic==1) for(int j=1;j<=m;j++) f(i,n,j,dic,ti-si+1); if(dic==2) for(int j=1;j<=m;j++) f(i,1,j,dic,ti-si+1); if(dic==3) for(int j=1;j<=n;j++) f(i,j,m,dic,ti-si+1); if(dic==4) for(int j=1;j<=n;j++) f(i,j,1,dic,ti-si+1); } cout< <
所以如果遇到类似的\(DP\)方程，可以考虑单调队列优化