https://www.luogu.com.cn/problem/P2254
https://darkbzoj.tk/problem/1499
单调队列优化dp
思路感觉比较简单，但也许是最近降智严重，代码实现的时候还自闭了一会/kk
\(N,M\le 200,k\le 200,T\le 40000\)
发现区间个数比较小，可以考虑从 \(k\) 开始入手，也就是挨个考虑每个时间区间的情况来转移
因为每个区间内倾斜方向相同，也就是这段时间内只能往一个方向走或不走
那么，\([s,t]\) 区间，它能朝着对应的倾斜方向走 \(0\sim t-s+1\) 步
所以设 \(f(now,i,j)\) 表示在第 \(now\) 个时间区间结束后，以坐标 \((i,j)\) 为终点，最多移动多少个格子
转移的式子以向上为例，那么 \(f(now,i,j)\) 由 \(f(now-1,[i-t+s-1,i],j)\) 转移来，其它方向当然也都相似
后面的 \(i-k\) 就是在本次区间内移动的距离
一开始脑子傻掉居然直接在代码里写成由 \(f(now,[i-t+s-1],j)\) 转移到 \(f(now,i,j)\) 。。。。果然还是要把转移方程在纸上好好写一遍在开始写代码
然后这样做复杂度是 \(O(kn^3)\)，超时，要用单调队列优化一下
发现单调队列里的数是一直在变化的（上面说的 \(i-k\) 造成的），不方便比较，但是可以比较它们的“相对大小”
什么意思呢，就是每次往单调队列里放入的数是 \(f(now-1,i,j)+wei\)，并每次让 \(wei\) 减一
原因：设 \(f(now-1,i,j)=f(now-1,i+1,j)+x\)，如果都要对一个 \((p,j)\) 来进行转移，那么 \(f(now-1,i,j)\) 会比 \(f(now-1,i+1,j)\) 转移后的结果多 \(x+1\)
当然是因为 \(p-i\) 比 \(p-(i+1)\) 多一
所以前面的一个数入队的时候，要比后面的数入队的时候多加一个 \(1\)
那么取队列中最大值的时候，也不能直接用队列的值（那只体现了相对的大小），而是用最大值对应的下标（设其为 \(ind\)）
则 \(f(now,i,j)=f(now-1,ind,j)+(i-ind)\)
所以复杂度就是 \(O(kn^2)\) 了
代码，同一函数复制四遍，不过感觉这样看起来似乎比通过不同参数调用同一函数来实现舒服，也更好写
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
inline int abs(int x){return x>0?x:-x;}
int head,tail;
int num[205],ind[205];
inline void push(int x,int index,int len){
while(tail<=head&&num[head]<=x) head--;
num[++head]=x;ind[head]=index;
while(tail<=head&&abs(index-ind[tail])>len) tail++;
}
int n,m;
int map[205][205];
int f[205][205][205];
char ss[205];
//up,down 都是把 i 放入队列的 ind
inline void work1(int now,int len){//up
for(reg int j=1;j<=m;j++){
tail=0;head=-1;
f[now][n][j]=std::max(f[now][n][j],f[now-1][n][j]);
int wei=12345;
push(f[now-1][n][j]+wei,n,len);wei--;
for(reg int i=n-1;i;i--){
if(!map[i][j]){
tail=0;head=-1;wei--;
push(-1e9,i,len);
}
else{
push(f[now-1][i][j]+wei,i,len);wei--;
f[now][i][j]=std::max(f[now][i][j],f[now-1][ind[tail]][j]+abs(i-ind[tail]));
}
}
}
}
inline void work2(int now,int len){//down
for(reg int j=1;j<=m;j++){
tail=0;head=-1;
f[now][1][j]=std::max(f[now][1][j],f[now-1][1][j]);
int wei=12345;
push(f[now-1][1][j]+wei,1,len);wei--;
for(reg int i=2;i<=n;i++){
if(!map[i][j]){
tail=0;head=-1;wei--;
push(-1e9,i,len);
}
else{
push(f[now-1][i][j]+wei,i,len);wei--;
f[now][i][j]=std::max(f[now][i][j],f[now-1][ind[tail]][j]+abs(i-ind[tail]));
}
}
}
}
//left,right 都是把 j 放入队列的 ind
inline void work3(int now,int len){//left
for(reg int i=1;i<=n;i++){
tail=0;head=-1;
f[now][i][m]=std::max(f[now][i][m],f[now-1][i][m]);
int wei=12345;
push(f[now-1][i][m]+wei,m,len);wei--;
for(reg int j=m-1;j;j--){
if(!map[i][j]){
tail=0;head=-1;wei--;
push(-1e9,j,len);
}
else{
push(f[now-1][i][j]+wei,j,len);wei--;
f[now][i][j]=std::max(f[now][i][j],f[now-1][i][ind[tail]]+abs(j-ind[tail]));
}
}
}
}
inline void work4(int now,int len){//right
for(reg int i=1;i<=n;i++){
tail=0;head=-1;
f[now][i][1]=std::max(f[now][i][1],f[now-1][i][1]);
int wei=12345;
push(f[now-1][i][1]+wei,1,len);wei--;
for(reg int j=2;j<=m;j++){
if(!map[i][j]){
tail=0;head=-1;wei--;
push(-1e9,j,len);
}
else{
push(f[now-1][i][j]+wei,j,len);wei--;
f[now][i][j]=std::max(f[now][i][j],f[now-1][i][ind[tail]]+abs(j-ind[tail]));
}
}
}
}
int main(){
n=read();m=read();int sx=read(),sy=read();
reg int k=read(),s,t,d;
for(reg int i=1;i<=n;i++){
std::scanf("%s",ss+1);
for(reg int j=1;j<=m;j++) map[i][j]=(ss[j]==‘.‘);
}
for(reg int aa=0;aa<=k;aa++)
for(reg int i=0;i<=n;i++)for(reg int j=0;j<=m;j++) f[aa][i][j]=-1e9;
f[0][sx][sy]=0;
for(reg int i=1;i<=k;i++){
s=read();t=read();d=read();
if(d==1) work1(i,t-s+1);//up
else if(d==2) work2(i,t-s+1);//down
else if(d==3) work3(i,t-s+1);//left
else work4(i,t-s+1);//right
}
int ans=0;
for(reg int i=1;i<=n;i++)for(reg int j=1;j<=m;j++) ans=std::max(ans,f[k][i][j]);
std::printf("%d",ans);
return 0;
}
原文：https://www.cnblogs.com/suxxsfe/p/13113500.html