Codeforces 586D Phillip and Trains（DP）

考虑相对位移。

每一轮人向右移动一格，再在竖直方向上移动0~1格，列车再向左移动两格。

这个过程相当于每一轮人向右移动一格，再在竖直方向上移动0~1格，然后人再向右移动两格。

然后就可以进行状态转移了。

f[i][j]表示能否走到i行j列的位置。最后在终点处查找是否存在f[i][ed]为1即可。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define rep(i,a,b)              for(int i(a); i <= (b); ++i)
 6 
 7 int f[31][1010];
 8 char st[31][1010];
 9 int T, n, k, ed;
10 bool flag;
11 
12 int main(){
13 
14     scanf("%d", &T);
15     for (; T--;){
16         scanf("%d%d", &n, &k);
17         memset(f, 0, sizeof f);
18         rep(i, 1, 3) scanf("%s", st[i] + 1);
19         rep(i, 1, 3) rep(j, n + 1, n + 10) st[i][j] = '.';
20         rep(i, 1, 3) st[i][n + 11] = '';
21         for (ed = 1; ed < n + 7; ) ed += 3;
22         rep(i, 1, 3) if (st[i][1] == 's') f[i][1] = 1, st[i][1] = '.';
23 
24         for (int j = 4; j <= ed; j += 3){
25             rep(i, 1, 3){
26                 if (st[i][j] != '.') continue;
27                 if (st[i][j - 1] != '.') continue;
28                 if (st[i][j - 2] != '.') continue;
29                 rep(k, i - 1, i + 1){
30                     if (k < 1 || k > 3) continue;
31                     if (st[k][j - 2] != '.') continue;
32                     if (st[k][j - 3] != '.') continue;
33                     f[i][j] |= f[k][j - 3];
34                 }
35             }
36         }
37 
38         flag = false;
39         rep(i, 1, 3) rep(j, n, ed)
40             if (f[i][j]){ flag = true; break;}
41 
42         puts(flag ? "YES" : "NO");
43 
44     }
45                         
46     return 0;
47 
48 }