c++ - 解决 Google Code Jam 2009 中的 "Welcome to Code Jam"

Question

我正在尝试解决以下代码堵塞问题，我取得了一些进展，但在少数情况下，我的代码给出了错误的输出。 Welcome to Code jam

所以我偶然发现了来自俄罗斯的开发人员“rem”的解决方案。我不知道他/她的解决方案是如何正常工作的……代码……

const string target = "welcome to code jam";

char buf[1<<20];

int main() {
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);

        gets(buf);
        FOR(test, 1, atoi(buf)) {
                gets(buf);
                string s(buf);
                int n = size(s);
                int k = size(target);
                vector<vector<int> > dp(n+1, vector<int>(k+1));
                dp[0][0] = 1;
                const int mod = 10000;
                assert(k == 19);
                REP(i, n) REP(j, k+1) {// Whats happening here
                        dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod;
                        if (j < k && s[i] == target[j])
                                dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%mod;
                }
                printf("Case #%d: %04d\n", test, dp[n][k]);
        }

        exit(0);
}//credit rem

有人可以解释一下这两个循环中发生了什么吗？

谢谢。

Answer 1

他在做什么:动态规划，到这里你也能看到。

他有二维数组，你需要了解它的语义。事实是 dp[i][j]计算他可以获得第一个 j 的子序列的方法数welcome to code jam的字母使用输入字符串中的所有字母直到第 i 个索引。两个索引都是基于 1 的，以允许不从字符串中获取任何字母的情况。

例如如果输入是:

welcome to code jjam

dp 的值在不同的情况下将是:

 dp[1][1] = 1; // first letter is w. perfect just the goal
 dp[1][2] = 0; // no way to have two letters in just one-letter string
 dp[2][2] = 1; // again: perfect
 dp[1][2] = 1; // here we ignore the e. We just need the w.
 dp[7][2] = 2; // two ways to construct we: [we]lcome and [w]elcom[e].

您具体询问的循环根据已计算的值计算新的动态值。