sol
首先有一个很显然的(O(nmT))的(dp)。
设(dp[t][i][j])表示(t)时刻钢琴移动到((i,j))位置的最长滑动距离。转移分滑动以及不动两种，判一下障碍物就可以了。
这样有50分。
然后发现100%的数据中(Kle200)，而且在每一段中转移都是完全一样的，就考虑把(O(nmT))的复杂度优化到(O(nmK))。
设(dp[t][i][j])表示第(t)个时间段末，钢琴在((i,j))位置的最长滑动距离。以(d=1)向上移动为例，这时(dp[t][i][j])应转移来自(dp[t-1][i...i+len][j])，其中(len)是这一时间段持续的长度。
分四种情况大力讨论一波即可。
单调队列优化转移。这是NOIP2017pj组的T4难度。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 205;
int n,m,x0,y0,k,s[N],t[N],d[N],hd,tl,q[N],dp[N][N][N],ans;
char map[N][N];
int main()
{
n=gi();m=gi();x0=gi();y0=gi();k=gi();
for (int i=1;i<=n;++i) scanf("%s",map[i]+1);
for (int i=1;i<=k;++i) s[i]=gi(),t[i]=gi(),d[i]=gi();
memset(dp,-63,sizeof(dp));
dp[0][x0][y0]=0;
for (int i=1;i<=k;++i)
{
int len=t[i]-s[i]+1;
if (d[i]==1)
for (int k=1;k<=m;++k)
{
hd=1;tl=0;
for (int j=n;j;--j)
{
if (map[j][k]=='x') {hd=1;tl=0;continue;}
while (hd<=tl&&q[hd]-j>len) ++hd;
if (hd<=tl) dp[i][j][k]=dp[i-1][q[hd]][k]+q[hd]-j;
while (hd<=tl&&dp[i-1][q[tl]][k]+q[tl]<=dp[i-1][j][k]+j) --tl;
q[++tl]=j;
}
}
if (d[i]==2)
for (int k=1;k<=m;++k)
{
hd=1;tl=0;
for (int j=1;j<=n;++j)
{
if (map[j][k]=='x') {hd=1;tl=0;continue;}
while (hd<=tl&&j-q[hd]>len) ++hd;
if (hd<=tl) dp[i][j][k]=dp[i-1][q[hd]][k]+j-q[hd];
while (hd<=tl&&dp[i-1][q[tl]][k]-q[tl]<=dp[i-1][j][k]-j) --tl;
q[++tl]=j;
}
}
if (d[i]==3)
for (int j=1;j<=n;++j)
{
hd=1;tl=0;
for (int k=m;k;--k)
{
if (map[j][k]=='x') {hd=1;tl=0;continue;}
while (hd<=tl&&q[hd]-k>len) ++hd;
if (hd<=tl) dp[i][j][k]=dp[i-1][j][q[hd]]+q[hd]-k;
while (hd<=tl&&dp[i-1][j][q[hd]]+q[hd]<=dp[i-1][j][k]+k) --tl;
q[++tl]=k;
}
}
if (d[i]==4)
for (int j=1;j<=n;++j)
{
hd=1;tl=0;
for (int k=1;k<=m;++k)
{
if (map[j][k]=='x') {hd=1;tl=0;continue;}
while (hd<=tl&&k-q[hd]>len) ++hd;
if (hd<=tl) dp[i][j][k]=dp[i-1][j][q[hd]]+k-q[hd];
while (hd<=tl&&dp[i-1][j][q[tl]]-q[tl]<=dp[i-1][j][k]-k) --tl;
q[++tl]=k;
}
}
for (int j=1;j<=n;++j)
for (int k=1;k<=m;++k)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
ans=max(ans,dp[k][i][j]);
printf("%d
",ans);
return 0;
}