BZOJ 1499 [NOI2005]瑰丽华尔兹 (单调队列优化DP)

题目大意：给你一个n*m棋盘(n,m<=200)，有一个人从给定的点s,e出发，有一些坏点不能走，一共给定k段连续的时间(k<=200)，在某一段时间之内它只能向一个给定的方向移动，在某一时刻，它可以移动或者不移动。求碰到坏点之前/总时间结束时，最长移动的距离。

朴素DP的方法是： $f[t][i][j]$ 表示在时间点t时，在位置(i,j)时已经走过的最长距离，i' j'表示这一步移动前的位置

得到方程 $f[t][i][j]=max(f[t][i][j],f[t-1][i'][j']+1)$

空间时间都会炸

那么重新定义 $f[k][i][j]$ 表示在第k个时间段，在位置(i,j)时已经走过的最长距离

那么显然 $f[k][i][j]=max(f[k-1][i'][j']+dis<(i',j'),(i,j)>)$ ，注意要根据移动的方向决定枚举的顺序

由于dis在同一行/列具有单调性，用队列随便优化一下就行了，如果dis大于t[i]-s[i]就删除队首，如果碰到障碍就清队列

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #define N 205
  5 using namespace std;
  6 
  7 int n,m,sx,sy,K,now,pst;
  8 int mp[N][N],st[N],ed[N],dir[N],que[N];
  9 int xx[]={0,-1,1,0,0},yy[]={0,0,0,-1,1};
 10 char str[N][N];
 11 int f[2][N][N];
 12 void upd1(int k)
 13 {
 14     int hd,tl;
 15     for(int j=1;j<=m;j++)
 16     {
 17         hd=1,tl=0;
 18         for(int i=n;i>=1;i--)
 19         {
 20             if(mp[i][j]) {hd=1,tl=0;continue;}
 21             while(hd<=tl&&f[pst][que[tl]][j]+que[tl]-i<=f[pst][i][j])
 22                 tl--;
 23             que[++tl]=i;
 24             while(hd<=tl&&que[hd]-i>ed[k]-st[k]+1)
 25                 hd++;
 26             f[now][i][j]=f[pst][que[hd]][j]+que[hd]-i;
 27         }
 28     }
 29 }
 30 void upd2(int k)
 31 {
 32     int hd,tl;
 33     for(int j=1;j<=m;j++)
 34     {
 35         hd=1,tl=0;
 36         for(int i=1;i<=n;i++)
 37         {
 38             if(mp[i][j]) {hd=1,tl=0;continue;}
 39             while(hd<=tl&&f[pst][que[tl]][j]+i-que[tl]<=f[pst][i][j])
 40                 tl--;
 41             que[++tl]=i;
 42             while(hd<=tl&&i-que[hd]>ed[k]-st[k]+1)
 43                 hd++;
 44             f[now][i][j]=f[pst][que[hd]][j]+i-que[hd];
 45         }
 46     }
 47 }
 48 void upd3(int k)
 49 {
 50     int hd,tl;
 51     for(int i=1;i<=n;i++)
 52     {
 53         hd=1,tl=0;
 54         for(int j=m;j>=1;j--)
 55         {
 56             if(mp[i][j]) {hd=1,tl=0;continue;}
 57             while(hd<=tl&&f[pst][i][que[tl]]+que[tl]-j<=f[pst][i][j])
 58                 tl--;
 59             que[++tl]=j;
 60             while(hd<=tl&&que[hd]-j>ed[k]-st[k]+1)
 61                 hd++;
 62             f[now][i][j]=f[pst][i][que[hd]]+que[hd]-j;
 63         }
 64     }
 65 }
 66 void upd4(int k)
 67 {
 68     int hd,tl;
 69     for(int i=1;i<=n;i++)
 70     {
 71         hd=1,tl=0;
 72         for(int j=1;j<=m;j++)
 73         {
 74             if(mp[i][j]) {hd=1,tl=0;continue;}
 75             while(hd<=tl&&f[pst][i][que[tl]]+j-que[tl]<=f[pst][i][j])
 76                 tl--;
 77             que[++tl]=j;
 78             while(hd<=tl&&j-que[hd]>ed[k]-st[k]+1)
 79                 hd++;
 80             f[now][i][j]=f[pst][i][que[hd]]+j-que[hd];
 81         }
 82     }
 83 }
 84 
 85 int main()
 86 {
 87     scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&K);
 88     for(int i=1;i<=n;i++){
 89         scanf("%s",str[i]+1);
 90         for(int j=1;j<=m;j++)
 91             if(str[i][j]=='x')
 92                 mp[i][j]=1;
 93     }
 94     for(int i=1;i<=K;i++)
 95         scanf("%d%d%d",&st[i],&ed[i],&dir[i]);
 96     memset(f,-0x3f,sizeof(f));
 97     f[0][sx][sy]=0;
 98     now=1,pst=0;
 99     for(int k=1;k<=K;k++)
100     {
101         if(dir[k]==1) upd1(k);
102         if(dir[k]==2) upd2(k);
103         if(dir[k]==3) upd3(k);
104         if(dir[k]==4) upd4(k);
105         swap(now,pst);
106     }
107     int ans=0;
108     for(int i=1;i<=n;i++)
109         for(int j=1;j<=m;j++)
110         ans=max(f[pst][i][j],ans);
111     printf("%d
",ans);
112     return 0;
113 }