2018 Yandex.Algorithm - Elimination Stage, Online Round 1

ultmaster

Problem D

题意：给一张贴好的邮票。问有哪些小邮票最后可以贴出这个图案。

题解：枚举所有子串。然后 check。check 的方法：题解的没看懂，自己想了一种：$dp(i+1,0)$ 表示到 $i$ 为止，左边的那段还没结束，也就是说不能接一段中间开始的（一定要接从头开始的）。可行为 1，不可行为 0；$dp(i+1,1)$ 表示到 $i$ 为止，左边的那段已经结束，可以接一段从中间开始的。这个一定要画个图理解一下！刚开始 $dp(0,0)=1$，最后如果 $dp(n,1)=1$ 则可行。更新的时候要利用最长公共后缀来更新，注意处理 min 和 max。

dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2; ++j) {
        if (!dp[i][j]) continue;
        if (j == 0) {
            step = min(lcs[i][st], ed - st);
            if (step == ed - st) dp[i + step][1] = 1;
        } else {
            step = 0;
            for (int k = st; k < ed; ++k) {
                int now_step = min(lcs[i][k], ed - k);
                if (now_step == ed - k) dp[i + now_step][1] = 1;
                step = max(step, now_step);
            }
        }
        for (int k = 1; k <= step; ++k)
            dp[i + k][0] = 1;
    }
}
return dp[n][1];