Codeforces Round #325D (Div. 2) (DP）

题目链接：

D. Phillip and Trains

分析：dp

我们先初始化，dp[i]表示当前列第i行是否可达，r[i]表示上一个dp值,接下来从头搜到尾

如果该位置满足s[i+1]=='.'且i<n，则用r[i]更新该位置的上面和下面一行，所以这是为什么数组开dp[5],r[5],

再判断该位置的i+2*k,i+2*k+1,i+2*k+2是否都是'.'，表示没有火车，处于安全位置

最后判断dp[1],dp[2],dp[3]是否可达，一个可达即输出yes

详情见代码

#include<cstdio>
#include<cstring> 

int t,n,k,dp[5],r[5];
char s[4][101];
bool check(int x,int y){ return x < n && (s[y][x] != '.');}
int max(int a,int b){ return a > b ? a : b; } 
int main()
{
    for(scanf("%d",&t); t--; )
    {
        scanf("%d %d",&n,&k);
        for(int i = 1; i <= 3; ++i)
        {
            scanf("%s",s[i]);
            r[i] = dp[i] = (s[i][0] == 's') && (s[i][1] == '.');
        }
        for(int k = 0,i = 1; i < n; ++i,++k)
        {
            for(int j = 1; j <= 3; ++j) if(!check(i+2*k,j))
            {
                dp[j-1] = max(dp[j-1],r[j]);
                dp[j+1] = max(dp[j+1],r[j]);
            }
            for(int j = 1; j <= 3; ++j) {if(check(i+2*k,j) || check(i+2*k+1,j) || check(i+2*k+2,j)) dp[j] = 0;r[j] = dp[j];}
        }
        if(dp[1] || dp[2] || dp[3]) puts("YES");else puts("NO");
    }
    return 0;
}