题目传送门 https://www.luogu.org/problemnew/show/P2254
在这先膜一波 \(\mathcal{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<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define inf 2147483647
- using 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<<ans<<endl;
- return 0;
- }
所以如果遇到类似的 \(DP\) 方程, 可以考虑单调队列优化
来源: http://www.bubuko.com/infodetail-3287069.html