#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,x,y,t,ans;
int f[201][201][201];
int b[5][2]={{},{-1},{1},{0,-1},{0,1}};
int oo_min=0x80000000;
char a[201][201];

inline void work_1(int t_i,int x,int y,int z,int d)
{
    int h=1,t=0,v=1;
    int q_1[201];
    int q_2[201];
    if (d==1)
        x=n;
    else if (d==2)
        x=1;
    else if (d==3)
        y=m;
    else if (d==4)
        y=1;
    while (1<=x&&x<=n&&1<=y&&y<=m)
    {
        if (a[x][y]=='x')
            h=1,t=0;
        else if (f[t_i-1][x][y]>oo_min)
        {
            while (h<=t&&f[t_i-1][x][y]-v>q_1[t])
                t--;
            t++;
            q_1[t]=f[t_i-1][x][y]-v,q_2[t]=v;
        }
        while (v-q_2[h]>z&&h<=t)
            h++;
        if (h<=t)
            f[t_i][x][y]=q_1[h]+v;
        else
            f[t_i][x][y]=oo_min;
        ans=max(ans,f[t_i][x][y]);
        x+=b[d][0],y+=b[d][1],v++;
    }
}

int main()
{
    while (~scanf("%d%d%d%d%d",&n,&m,&x,&y,&t))
    {
        for (int i=1;i<=n;i++)
        {
            char c;
            scanf("%c",&c);
            for (int j=1;j<=m;j++)
                scanf("%c",&a[i][j]),f[0][i][j]=oo_min;
        }
        ans=f[0][x][y]=0;
        for (int t_i=1;t_i<=t;t_i++)
        {
            int s,e,d;
            scanf("%d%d%d",&s,&e,&d);
            if (d==1||d==2)
            {
                for (int i=1;i<=m;i++)
                    work_1(t_i,0,i,e-s+1,d);
            }
            else
            {
                for (int i=1;i<=n;i++)
                    work_1(t_i,i,0,e-s+1,d);
            }
        }
        printf("%d\n",ans);
    }
}

####Block Code
//其实私以为代码写得过于丑陋...东南西北不应该分为四个函数讨论
//所以虽然复杂度是O(N^2*K)，但我还是觉得特玄...
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200+5;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int n,m,x0,y0,K;
bool map[N][N];
int dp[N][N];
struct Eve {
//1、2、3、4 依次表示 北、南、西、东
int st,ed,dir;
}e[N];
struct node1 {
int s,v;
node1(int s=0,int v=0):s(s),v(v){}
};
struct DQue {
node1 a[N];
int l,r;
inline bool empty() {return l==r;}
inline void clear() {l=r=0;}
inline int get() {return a[l+1].v;}
inline void push(const node1&tp) {
while(l!=r&&a[r].v<tp.v) --r;
a[++r]=tp;
}
inline void del(int s) {
while(l!=r&&a[l+1].s<=s) ++l;
}
}que;
void Init() {
scanf("%d%d%d%d%d",&n,&m,&y0,&x0,&K);
char str[N];
for(int i=1;i<=n;++i) {
scanf("%s",str);
for(int j=0;j<m;++j)
map[i][j+1]= str[j]=='x'?1:0;
}
for(int i=0;i<K;++i)
scanf("%d%d%d",&e[i].st,&e[i].ed,&e[i].dir);
}
inline void do_north(int len) {
for(int i=1; i<=m; ++i) {
que.clear();
for(int j=n; j; --j) {
if(map[j][i]) {
que.clear();
continue;
} else if(que.empty()) {
if(dp[j][i]!=0xf1f1f1f1)
que.push(node1(n-j,dp[j][i]-n+j));
continue;
}
int tmp=dp[j][i];
dp[j][i]=max(dp[j][i],que.get()+n-j);
if(tmp!=0xf1f1f1f1)
que.push(node1(n-j,tmp-n+j));
que.del(n-j-len);
}
}
}
inline void do_south(int len) {
for(int i=1;i<=m;++i) {
que.clear();
for(int j=1;j<=n;++j) {
if(map[j][i]) {
que.clear();
continue;
} else if(que.empty()) {
if(dp[j][i]!=0xf1f1f1f1)
que.push(node1(j,dp[j][i]-j));
continue;
}
int tmp=dp[j][i];
dp[j][i]=max(dp[j][i],que.get()+j);
if(tmp!=0xf1f1f1f1)
que.push(node1(j,tmp-j));
que.del(j-len);
}
}
}
inline void do_west(int len) {
for(int i=1;i<=n;++i) {
que.clear();
for(int j=m; j; --j) {
if(map[i][j]) {
que.clear();
continue;
} else if(que.empty()) {
if(dp[i][j]!=0xf1f1f1f1)
que.push(node1(m-j,dp[i][j]-m+j));
continue;
}
int tmp=dp[i][j];
dp[i][j]=max(dp[i][j],que.get()+m-j);
if(tmp!=0xf1f1f1f1)
que.push(node1(m-j,tmp-m+j));
que.del(m-j-len);
}
}
}
inline void do_east(int len) {
for(int i=1;i<=n;++i) {
que.clear();
for(int j=1;j<=m;++j) {
if(map[i][j]) {
que.clear();
continue;
} else if(que.empty()) {
if(dp[i][j]!=0xf1f1f1f1)
que.push(node1(j,dp[i][j]-j));
continue;
}
int tmp=dp[i][j];
dp[i][j]=max(dp[i][j],que.get()+j);
if(tmp!=0xf1f1f1f1)
que.push(node1(j,tmp-j));
que.del(j-len);
}
}
}
void Solve() {
memset(dp,0xf1,sizeof(dp));
dp[y0][x0]=0;
for(int i=0;i<K;++i) {
int tm=e[i].ed-e[i].st+1;
switch(e[i].dir) {
case 1:do_north(tm); break;
case 2:do_south(tm); break;
case 3:do_west(tm); break;
case 4:do_east(tm); break;
}
}
int ans=-inf;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans=max(ans,dp[i][j]);
printf("%d\n",ans);
}
int main() {
// freopen("tmp.txt","r",stdin);
Init();
Solve();
return 0;
}

时间、空间还好吧。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 976 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 980 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 980 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 976 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 980 KiB, score = 10
测试数据 #8: Accepted, time = 125 ms, mem = 980 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 984 KiB, score = 10
Accepted, time = 530 ms, mem = 984 KiB, score = 100

上下左右单开了方法、、、、应该还有方法省掉大堆重复代码

Block Code

#include <cstdio>
#include <algorithm>
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define MAX 205

int dp[2][MAX][MAX];
int c[MAX][MAX], d = 0;
int p[MAX], q[MAX], f, r, n, m;

char getValidChar() {
char ch = getchar();
while(ch != 'x' && ch != '.') ch = getchar();
return ch;
}

void up(int l) {
int i, j;
FOR(j,1,m) {
f = r = 0;
FORD(i,n,1) {
dp[d][i][j] = dp[1-d][i][j];
if(c[i][j] == 'x') {
f = r = 0;
continue;
}
if(dp[1-d][i][j] != -1) {
while(f < r && dp[1-d][i][j] + i >= q[r-1]) r--;
q[r] = dp[1-d][i][j] + i;
p[r] = i;
r++;
}
while(f < r && p[f]-i > l) f++;
if(f < r) dp[d][i][j] = max(dp[d][i][j], q[f] - i);
}
}
}

void down(int l) {
int i, j;
FOR(j,1,m) {
f = r = 0;
FOR(i,1,n) {
dp[d][i][j] = dp[1-d][i][j];
if(c[i][j] == 'x') {
f = r = 0;
continue;
}
if(dp[1-d][i][j] != -1) {
while(f < r && dp[1-d][i][j] - i >= q[r-1]) r--;
q[r] = dp[1-d][i][j] - i;
p[r] = i;
r++;
}
while(f < r && i-p[f] > l) f++;
if(f < r) dp[d][i][j] = max(dp[d][i][j], q[f] + i);
}
}
}

void left(int l) {
int i, j;
FOR(i,1,n) {
f = r = 0;
FORD(j,m,1) {
dp[d][i][j] = dp[1-d][i][j];
if(c[i][j] == 'x') {
f = r = 0;
continue;
}
if(dp[1-d][i][j] != -1) {
while(f < r && dp[1-d][i][j] + j >= q[r-1]) r--;
q[r] = dp[1-d][i][j] + j;
p[r] = j;
r++;
}
while(f < r && p[f]-j > l) f++;
if(f < r) dp[d][i][j] = max(dp[d][i][j], q[f] - j);
}
}
}

void right(int l) {
int i, j;
FOR(i,1,n) {
f = r = 0;
FOR(j,1,m) {
dp[d][i][j] = dp[1-d][i][j];
if(c[i][j] == 'x') {
f = r = 0;
continue;
}
if(dp[1-d][i][j] != -1) {
while(f < r && dp[1-d][i][j] - j >= q[r-1]) r--;
q[r] = dp[1-d][i][j] - j;
p[r] = j;
r++;
}
while(f < r && j-p[f] > l) f++;
if(f < r) dp[d][i][j] = max(dp[d][i][j], q[f] + j);
}
}
}

int main() {
int x, y, k, t, s, i, j, o;

scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
FOR(i,1,n) FOR(j,1,m) {
c[i][j] = getValidChar();
dp[d][i][j] = -1;
}
dp[d][x][y] = 0;

while(k--) {
d = 1 - d;
scanf("%d%d%d", &s, &t, &o);
switch(o) {
case 1: up(t-s+1); break;
case 2: down(t-s+1); break;
case 3: left(t-s+1); break;
case 4: right(t-s+1); break;
}
}

int ans = 0;
FOR(i,1,n) FOR(j,1,m)
ans=max(ans,dp[d][i][j]);
printf("%d", ans);

return 0;
}

动态规划+单调队列优化（感觉这次的DP写丑了。。。好长555）
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 36748 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 36756 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 36752 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 36756 KiB, score = 10
测试数据 #4: Accepted, time = 124 ms, mem = 36752 KiB, score = 10
测试数据 #5: Accepted, time = 187 ms, mem = 36752 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 36756 KiB, score = 10
测试数据 #7: Accepted, time = 280 ms, mem = 36756 KiB, score = 10
测试数据 #8: Accepted, time = 187 ms, mem = 36752 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 36752 KiB, score = 10
Accepted, time = 1089 ms, mem = 36756 KiB, score = 100

//-------------------------------------------------------------------------------------

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>

using namespace std ;

#define MAXN 210
#define MAXK 210
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define dow( i , x ) for ( int i = x ; i ; -- i )

char map[ MAXN ][ MAXN ] ;
int f[ MAXN ][ MAXN ][ MAXN ] , n , m , k , x , y ;

deque < int > Q ;

int main( ) {
scanf( "%d%d%d%d%d" , &n , &m , &x , &y , &k ) ;
rep( i , n ) scanf( "%s" , map[ i ] + 1 ) ;
rep( i , n ) rep( j , m ) f[ 0 ][ i ][ j ] = - 1 ;
f[ 0 ][ x ][ y ] = 0 ;
rep( h , k ) {
int l , r , d ; scanf( "%d%d%d" , &l , &r , &d ) ;
rep( i , n ) rep( j , m ) f[ h ][ i ][ j ] = - 1 ;
if ( d == 1 ) {
rep( j , m ) {
Q.clear( ) ;
dow( i , n ) if ( map[ i ][ j ] == '.' ) {
while ( ! Q.empty( ) && Q.front( ) - i > r - l + 1 ) Q.pop_front( ) ;
if ( f[ h - 1 ][ i ][ j ] != - 1 ) {
while ( ! Q.empty( ) && Q.back( ) - i + f[ h - 1 ][ Q.back( ) ][ j ] <= f[ h - 1 ][ i ][ j ] ) Q.pop_back( ) ;
Q.push_back( i ) ;
}
if ( ! Q.empty( ) ) f[ h ][ i ][ j ] = f[ h - 1 ][ Q.front( ) ][ j ] + Q.front( ) - i ;
else f[ h ][ i ][ j ] = - 1 ;
} else {
Q.clear( ) ; f[ h ][ i ][ j ] = - 1 ;
}
}
} else if ( d == 2 ) {
rep( j , m ) {
Q.clear( ) ;
rep( i , n ) if ( map[ i ][ j ] == '.' ) {
while ( ! Q.empty( ) && i - Q.front( ) > r - l + 1 ) Q.pop_front( ) ;
if ( f[ h - 1 ][ i ][ j ] != - 1 ) {
while ( ! Q.empty( ) && i - Q.back( ) + f[ h - 1 ][ Q.back( ) ][ j ] <= f[ h - 1 ][ i ][ j ] ) Q.pop_back( ) ;
Q.push_back( i ) ;
}
if ( ! Q.empty( ) ) f[ h ][ i ][ j ] = f[ h - 1 ][ Q.front( ) ][ j ] + i - Q.front( ) ;
else f[ h ][ i ][ j ] = - 1 ;
} else {
Q.clear( ) ; f[ h ][ i ][ j ] = - 1 ;
}
}
} else if ( d == 3 ) {
rep( i , n ) {
Q.clear( ) ;
dow( j , m ) if ( map[ i ][ j ] == '.' ) {
while ( ! Q.empty( ) && Q.front( ) - j > r - l + 1 ) Q.pop_front( ) ;
if ( f[ h - 1 ][ i ][ j ] != - 1 ) {
while ( ! Q.empty( ) && Q.back( ) - j + f[ h - 1 ][ i ][ Q.back( ) ] <= f[ h - 1 ][ i ][ j ] ) Q.pop_back( ) ;
Q.push_back( j ) ;
}
if ( ! Q.empty( ) ) f[ h ][ i ][ j ] = Q.front( ) - j + f[ h - 1 ][ i ][ Q.front( ) ] ;
else f[ h ][ i ][ j ] = - 1 ;
} else {
Q.clear( ) ; f[ h ][ i ][ j ] = - 1 ;
}
}
} else {
rep( i , n ) {
Q.clear( ) ;
rep( j , m ) if ( map[ i ][ j ] == '.' ) {
while ( ! Q.empty( ) && j - Q.front( ) > r - l + 1 ) Q.pop_front( ) ;
if ( f[ h - 1 ][ i ][ j ] != - 1 ) {
while ( ! Q.empty( ) && j - Q.back( ) + f[ h - 1 ][ i ][ Q.back( ) ] <= f[ h - 1 ][ i ][ j ] ) Q.pop_back( ) ;
Q.push_back( j ) ;
}
if ( ! Q.empty( ) ) f[ h ][ i ][ j ] = j - Q.front( ) + f[ h - 1 ][ i ][ Q.front( ) ] ;
else f[ h ][ i ][ j ] = - 1 ;
} else {
Q.clear( ) ; f[ h ][ i ][ j ] = - 1 ;
}
}
}
}
int ans = 0 ;
rep( i , n ) rep( j , m ) ans = max( ans , f[ k ][ i ][ j ] ) ;
printf( "%d\n" , ans ) ;
return 0 ;
}

终于过了……
为了此题的单调队列，我写了将近两整天的时间，才艰难地调出来，这是我过的第一道NOI题（我还是太弱了……）。这道题是一场比赛里遇到的，刚看到就被吓崩了，后来硬着头皮看解题报告加上瞎琢磨，又犯了各种各样的低级错误，终于过了。
解法1：在每个时间枚举使用或不使用魔法，再加一点优化。时间复杂度：O( 2 ^ n )，期望得分：30分。
解法2：DP，简单分析可以根据坐标和时间列出状态转移方程式dp[i][j][k]（当前坐标，代表使用魔法次数）=min(dp[i-1（依方向而定）][j][k-1]（不使用魔法）,dp[i][j][k-1]+1（使用魔法）)，其中i,j代表坐标，k代表时间。注意，此解法需要开三维数组，大数据一定会越界，所以怎么样定义数组要注意，对得分影响很大。时间复杂度O( nmt )，期望得分：50分。
解法3：DP+单调队列优化，由于每个时间段只能向一个方向移动，可得到状态转移方程式dp[i][j][k]（代表使用魔法次数）=dp[i-r（依方向而定）][j][k-1]+t（k时间段的总时间）-(i-r)（移动过程耗费的时间）。然后发现此方程可以化为dp[i][j][k]=(dp[i-r][j][k-1]+r)+(t-i)，可以用单调队列优化。在移动的那个方向上，显然dp[i-r][j][k-1]+r是可以找到最大值的，那么只要用单调队列记录最大值，每一次求出r的时间就可以基本降为O(1)，这样时间复杂度O( nmk )，期望得分：100分。
只好贴上我丑陋无比的代码了……
#include <cstdio>
#include <cstring>
#include <algorithm>
#define SIZE 201

using namespace std;
int dp[ SIZE ][ SIZE ][ SIZE ];
int dir[ SIZE ][ 2 ], ti[ SIZE ];//dir每个时间段的方向，t每个时间段的持续时间
bool mp[ SIZE ][ SIZE ];//存储地图
int q[ SIZE ], val[ SIZE ];//单调队列
int n, m, sx, sy, p, ans = 1 << 30, head, tail, tim = 0;
void add ( int a, int b )//向单调队列添加元素
{
if ( a - b == -1 ) return ;
if ( a <= q[ head ] )//可插入头，则将其后面元素清除
{
head = tail = 1;
q[ head ] = a;
val[ head ] = b;
return ;
}
if ( a > q[ tail ] )//插入尾
{
tail ++;
q[ tail ] = a;
val[ tail ] = b;
return ;
}
for ( int i = head; i < tail; i ++ )//若不在头尾则向中间插入
{
if ( q[ i ] < a && q[ i + 1 ] >= a )
{
for ( int j = tail + 1; j > i + 1; j -- )
{
q[ j ] = q[ j - 1 ];
val[ j ] = val[ j - 1 ];
}
q[ i + 1 ] = a;
val[ i + 1 ] = b;
break;
}
}
tail ++;
}
int main()
{
memset ( dp, -1, sizeof ( dp ) );
memset ( mp, true, sizeof ( mp ) );
char s[ 300 ];
int t1, t2, t3;
scanf ( "%d%d%d%d%d", &n, &m, &sx, &sy, &p );
dp[ sx ][ sy ][ 0 ] = 0;
for ( int i = 1; i <= n; i ++ )
{
scanf ( "%s", s );
for ( int j = 1; j <= m; j ++ )
if ( s[ j - 1 ] == '.' ) mp[ i ][ j ] = false;
}
for ( int i = 1; i <= p; i ++ )//处理每个时间段的方向
{
scanf ( "%d%d%d", &t1, &t2, &t3 );
switch ( t3 )
{
case 1: dir[ i ][ 0 ] = -1; break;
case 2: dir[ i ][ 0 ] = 1; break;
case 3: dir[ i ][ 1 ] = -1; break;
case 4: dir[ i ][ 1 ] = 1; break;
}
ti[ i ] = t2 - t1 + 1;
tim = max ( tim, t2 );
}
q[ 0 ] = 1 << 30;
val[ 0 ] = -1;
for ( int k = 1; k <= p; k ++ )
{
if ( dir[ k ][ 0 ] != 0 )//若沿列移动
for ( int j = 1; j <= m; j ++ )
{
head = tail = 0;//初始化队列
for ( int i = 1; i <= n; i ++ )
{
int x, y = j;//处理坐标
if ( dir[ k ][ 0 ] == -1 ) x = n - i + 1;
else x = i;
if ( mp[ x ][ y ] )//若遇到障碍物，清除队列
{
head = tail = 0;
continue;
}
add ( dp[ x ][ y ][ k - 1 ] + i, i );
int tz = q[ head ] + ti[ k ] - i;

if ( dp[ x ][ y ][ k ] > tz || dp[ x ][ y ][ k ] == -1 ) dp[ x ][ y ][ k ] = tz;//状态转移
while ( i - val[ head ] >= ti[ k ] )//处理从队列头存储的点能否到达下一个要处理的点
{
head ++;
if ( head > tail )
{
head = tail = 0;
break;
}
}
if ( k == p && ans > dp[ x ][ y ][ k ] && dp[ x ][ y ][ k ] != -1 ) ans = dp[ x ][ y ][ k ];//处理答案
}
}
else//处理沿行移动，与上面基本相同
for ( int i = 1; i <= n; i ++ )
{
head = tail = 0;
for ( int j = 1; j <= m; j ++ )
{
int x = i, y;
if ( dir[ k ][ 1 ] == -1 ) y = m - j + 1;
else y = j;
if ( mp[ x ][ y ] )
{
head = tail = 0;
continue;
}
add ( dp[ x ][ y ][ k - 1 ] + j, j );
if ( head == 0 ) continue;
int tz = q[ head ] + ti[ k ] - j;
if ( dp[ x ][ y ][ k ] > tz || dp[ x ][ y ][ k ] == -1 ) dp[ x ][ y ][ k ] = tz;
while ( j - val[ head ] >= ti[ k ] )
{
head ++;
if ( head > tail )
{
head = tail = 0;
break;
}
}
if ( k == p && ans > dp[ x ][ y ][ k ] && dp[ x ][ y ][ k ] != -1 ) ans = dp[ x ][ y ][ k ];
}
}
}
printf ( "%d\n", tim - ans );
return 0;
}

val[ j ] = val[ j - 1 ];
}
q[ i + 1 ] = a;
val[ i + 1 ] = b;
break;
}
}
tail ++;
}
int main()
{
memset ( dp, -1, sizeof ( dp ) );
memset ( mp, true, sizeof ( mp ) );
char s[ 300 ];
int t1, t2, t3;
scanf ( "%d%d%d%d%d", &n, &m, &sx, &sy, &p );
dp[ sx ][ sy ][ 0 ] = 0;
for ( int i = 1; i <= n; i ++ )
{
scanf ( "%s", s );
for ( int j = 1; j <= m; j ++ )
if ( s[ j - 1 ] == '.' ) mp[ i ][ j ] = false;
}
for ( int i = 1; i <= p; i ++ )//处理每个时间段的方向
{
scanf ( "%d%d%d", &t1, &t2, &t3 );
switch ( t3 )
{
case 1: dir[ i ][ 0 ] = -1; break;
case 2: dir[ i ][ 0 ] = 1; break;
case 3: dir[ i ][ 1 ] = -1; break;
case 4: dir[ i ][ 1 ] = 1; break;
}
ti[ i ] = t2 - t1 + 1;
tim = max ( tim, t2 );
}
q[ 0 ] = 1 << 30;
val[ 0 ] = -1;
for ( int k = 1; k <= p; k ++ )
{
if ( dir[ k ][ 0 ] != 0 )//若沿列移动
for ( int j = 1; j <= m; j ++ )
{
head = tail = 0;//初始化队列
for ( int i = 1; i <= n; i ++ )
{
int x, y = j;//处理坐标
if ( dir[ k ][ 0 ] == -1 ) x = n - i + 1;
else x = i;
if ( mp[ x ][ y ] )//若遇到障碍物，清除队列
{
head = tail = 0;
continue;
}
add ( dp[ x ][ y ][ k - 1 ] + i, i );
int tz = q[ head ] + ti[ k ] - i;

if ( dp[ x ][ y ][ k ] > tz || dp[ x ][ y ][ k ] == -1 ) dp[ x ][ y ][ k ] = tz;//状态转移
while ( i - val[ head ] >= ti[ k ] )//处理从队列头存储的点能否到达下一个要处理的点
{
head ++;
if ( head > tail )
{
head = tail = 0;
break;
}
}
if ( k == p && ans > dp[ x ][ y ][ k ] && dp[ x ][ y ][ k ] != -1 ) ans = dp[ x ][ y ][ k ];//处理答案
}
}
else//处理沿行移动，与上面基本相同
for ( int i = 1; i <= n; i ++ )
{
head = tail = 0;
for ( int j = 1; j <= m; j ++ )
{
int x = i, y;
if ( dir[ k ][ 1 ] == -1 ) y = m - j + 1;
else y = j;
if ( mp[ x ][ y ] )
{
head = tail = 0;
continue;
}
add ( dp[ x ][ y ][ k - 1 ] + j, j );
if ( head == 0 ) continue;
int tz = q[ head ] + ti[ k ] - j;
if ( dp[ x ][ y ][ k ] > tz || dp[ x ][ y ][ k ] == -1 ) dp[ x ][ y ][ k ] = tz;
while ( j - val[ head ] >= ti[ k ] )
{
head ++;
if ( head > tail )
{
head = tail = 0;
break;
}
}
if ( k == p && ans > dp[ x ][ y ][ k ] && dp[ x ][ y ][ k ] != -1 ) ans = dp[ x ][ y ][ k ];
}
}
}
printf ( "%d\n", tim - ans );
return 0;
}