【传送门：BZOJ1499】
简要题意：
有一个字符矩阵，'.'表示能走，'x'表示不能走，给出起点的坐标，起点有一座钢琴，每单位时间可以移动一格，共有k个时间段，然后再给出每个时间段起始时间和结束时间，以及当前时间段能够移动的方向。而在某个时间，可以控制钢琴不动，钢琴不能走到'x'而且不能走出矩阵
求出钢琴最多能走多少格
题解：
一眼DP题
设f[t][i][j]表示第t时间走到(i,j)最多能走的格数，f[t][i][j]=max(f[t-1][i][j],f[t-1][i-dx[i]][j-dy[i]]+1)，时间复杂度O(nmT)，超时
我们重新搞DP方程，设f[k][i][j]表示第k时间段走到(i,j)最多能走的格数，f[k][i][j]=max(f[k][i][j],f[k-1][i-dx[i]*c][j-dy[i]*c]+c)，c为第k-1时间段走多长时间
因为每个时间段都是对于一行或者一列进行操作的，所以我们可以分成四种情况来单调队列
这样子时间复杂度就是O(nmk)
还要提的一点是，最好用滚动数组，优化一下空间
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; char st[210][210]; struct node { int d,t; }T[210]; int f[2][210][210]; int list[210]; int main() { int n,m,x,y,k; scanf("%d%d%d%d%d",&n,&m,&x,&y,&k); for(int i=1;i<=n;i++) scanf("%s",st[i]+1); for(int i=1;i<=k;i++) { int l,r; scanf("%d%d%d",&l,&r,&T[i].t); T[i].d=r-l+1; } memset(f,-63,sizeof(f)); f[0][x][y]=0; int now=0,last=1,head,tail; for(int K=1;K<=k;K++) { now^=1;last^=1; if(T[K].t==1) { for(int j=1;j<=m;j++) { head=1;tail=0; for(int i=n;i>=1;i--) { if(st[i][j]=='x') head=1,tail=0; while(head<=tail&&list[head]-i>T[K].d) head++; if(head<=tail) f[now][i][j]=f[last][list[head]][j]+list[head]-i; while(head<=tail&&f[last][i][j]>f[last][list[tail]][j]+list[tail]-i) tail--; list[++tail]=i; f[now][i][j]=max(f[now][i][j],f[last][i][j]); } } } if(T[K].t==2) { for(int j=1;j<=m;j++) { head=1;tail=0; for(int i=1;i<=n;i++) { if(st[i][j]=='x') head=1,tail=0; while(head<=tail&&i-list[head]>T[K].d) head++; if(head<=tail) f[now][i][j]=f[last][list[head]][j]+i-list[head]; while(head<=tail&&f[last][i][j]>f[last][list[tail]][j]+i-list[tail]) tail--; list[++tail]=i; f[now][i][j]=max(f[now][i][j],f[last][i][j]); } } } if(T[K].t==3) { for(int i=1;i<=n;i++) { head=1;tail=0; for(int j=m;j>=1;j--) { if(st[i][j]=='x') head=1,tail=0; while(head<=tail&&list[head]-j>T[K].d) head++; if(head<=tail) f[now][i][j]=f[last][i][list[head]]+list[head]-j; while(head<=tail&&f[last][i][j]>f[last][i][list[tail]]+list[tail]-j) tail--; list[++tail]=j; f[now][i][j]=max(f[now][i][j],f[last][i][j]); } } } if(T[K].t==4) { for(int i=1;i<=n;i++) { head=1;tail=0; for(int j=1;j<=m;j++) { if(st[i][j]=='x') head=1,tail=0; while(head<=tail&&j-list[head]>T[K].d) head++; if(head<=tail) f[now][i][j]=f[last][i][list[head]]+j-list[head]; while(head<=tail&&f[last][i][j]>f[last][i][list[tail]]+j-list[tail]) tail--; list[++tail]=j; f[now][i][j]=max(f[now][i][j],f[last][i][j]); } } } } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(f[now][i][j],ans); printf("%d ",ans); return 0; }