题外话：题目极好，做题体验极差

题面：

题解：

F[t][i][j]表示第t时刻钢琴位于(i,j)时的最大路程

F[t][i][j]=max(F[t-1][i][j],F[t-1][a][b]+1) (mp[i][j]可以到达，(a,b)直接到(i,j)之间没有家具，即路径合法)

因为船的倾斜是连续的，所以可以考虑按时间段来进行dp

F[t][i][j]表示前t个时间段结束后，钢琴位于(i,j)的最大路程

F[t][i][j]=max(F[t][i][j],F[t-1][a][b]+Dis(a,b,i,j)) (mp[i][j]可达,Dis(a,b,i,j)<=T[t]-S[t]+1，(a,b)直接到(i,j)之间没有家具，即路径合法)

考虑使用单调队列优化dp

以下“OK”意味着mp[i][j]不出地图，且（i,j）上无家具，是可以到达的合法位置，且路径合法

路径合法可以通过在单调队列时遇到mp[i][j]=='x'的情况直接清空队列来快速实现，当然也可以通过写前缀和来判断实现

注意在写单调队列时入队应该放在维护F[t][i][j]前，因为可以停留在(i,j)

Case 1:D[t]==1

此时船向北倾斜，则b=j（i大到i小）

F[t][i][j]=max(F[t][i][j],F[t-1][a][j]+a-i) (OK,a-i<=T[t]-S[t]+1)

即维护：max(F[t-1][a][j]+a)-i (a<=T[t]-S[t]+1+i)

Case 2:D[t]==2

此时船向南倾斜，则b=j（i小到i大）

F[t][i][j]=max(F[t][i][j],F[t-1][a][j]+i-a) (OK,i-a<=T[t]-S[t]+1)

即维护：max(F[t-1][a][j]-a)+i (a>=i-T[t]+S[t]-1)

Case 3:D[t]==3

此时船向西倾斜，则a=i（j从大到小）

F[t][i][j]=max(F[t][i][j],F[t-1][i][b]+b-j) (OK,b-j<=T[t]-S[t]+1)

即维护：max(F[t-1][i][b]+b)-j（b<=T[t]-S[t]+1+j）

Case 4:D[t]==4

此时船向东倾斜，则a=i（j从小到大）

F[t][i][j]=max(F[t][i][j],F[t-1][i][b]+j-b) (OK,j-b<=T[t]-S[t]+1)

即维护：max(F[t-1][i][b]-b)+j (b>=j-T[t]+S[t]-1)

对以上使用单调队列进行优化

代码：

1 #include
      
        2 #include
       
         3 #define max(a,b) ((a)>(b)?(a):(b)) 4 #define min(a,b) ((a)<(b)?(a):(b)) 5 using namespace std; 6 const int maxn=205,maxm=205,maxk=205,maxt=4e4+5; 7 const int inf=1<<30; 8 int N,M,K,X0,Y0,S[maxk],T[maxk],D[maxk]; 9 int F[maxk][maxn][maxm],f1,f2,ans=0;10 char mp[maxn][maxm];11 struct Node{ int data,x; }que[maxn];12 int main(){13     scanf("%d%d%d%d%d",&N,&M,&X0,&Y0,&K);14     for(int i=1;i<=N;i++)15         scanf("%s",mp[i]+1);16     for(int i=1;i<=K;i++)17         scanf("%d%d%d",&S[i],&T[i],&D[i]);18     for(int t=0;t<=K;t++)19         for(int i=0;i<=N;i++)20             for(int j=0;j<=M;j++)21                 F[t][i][j]=-inf;22     for(int t=0;t<=K;t++)23         F[t][X0][Y0]=0;24     for(int t=1;t<=K;t++){25         if(D[t]==1){26             for(int j=1;j<=M;j++){27                 f1=1,f2=0;            28                 for(int i=N;i>=1;i--){29                     if(mp[i][j]=='x') {30                         f1=1,f2=0;31                         continue;32                     }33                     while(f1<=f2 && que[f1].x>T[t]-S[t]+1+i) f1++;34                     while(f1<=f2 && F[t-1][i][j]+i>=que[f2].data) f2--;35                     que[++f2].data=F[t-1][i][j]+i; que[f2].x=i;36                     if(f1<=f2) F[t][i][j]=max(F[t][i][j],que[f1].data-i);                    37                 }38             }39         }40         else if(D[t]==2){41             for(int j=1;j<=M;j++){42                 f1=1,f2=0;        43                 for(int i=1;i<=N;i++){44                     if(mp[i][j]=='x') {45                         f1=1,f2=0;46                         continue;47                     }48                     while(f1<=f2 && que[f1].x
        
         =que[f2].data) f2--;50                     que[++f2].data=F[t-1][i][j]-i; que[f2].x=i;51                     if(f1<=f2) F[t][i][j]=max(F[t][i][j],que[f1].data+i);                    52                 }53             }54         }55         else if(D[t]==3){56             for(int i=1;i<=N;i++){57                 f1=1,f2=0;58                 for(int j=M;j>=1;j--){59                     if(mp[i][j]=='x') {60                         f1=1,f2=0;61                         continue;62                     }63                     while(f1<=f2 && que[f1].x>T[t]-S[t]+1+j) f1++;64                     while(f1<=f2 && F[t-1][i][j]+j>=que[f2].data) f2--;65                     que[++f2].data=F[t-1][i][j]+j; que[f2].x=j;66                     if(f1<=f2) F[t][i][j]=max(F[t][i][j],que[f1].data-j);                    67                 }68             }69         }70         else{
    // D[t]==471             for(int i=1;i<=N;i++){72                 f1=1,f2=0;73                 for(int j=1;j<=M;j++){74                     if(mp[i][j]=='x') {75                         f1=1,f2=0;76                         continue;77                     }78                     while(f1<=f2 && que[f1].x
         
          =que[f2].data) f2--;80                     que[++f2].data=F[t-1][i][j]-j; que[f2].x=j;81                     if(f1<=f2) F[t][i][j]=max(F[t][i][j],que[f1].data+j);                    82                 }83             }84         }85     }86     for(int i=1;i<=N;i++)87         for(int j=1;j<=M;j++)88             ans=max(ans,F[K][i][j]);89     printf("%d\n",ans);90     return 0;91 }
         
        
       
      

---

By：AlenaNuna