从Google Code Jam 2009解决“欢迎使用Code Jam”

Question

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

所以我偶然发现了一个来自俄罗斯的dev "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

他在做什么:动态编程，到目前为止你也可以看到。

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

例如，如果输入为：

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].

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

Answer 2

哇，几天前我在练习这个问题，偶然发现了这个问题。

我怀疑，如果你没有学习过DP，那么说“他在做动态编程”并不能解释太多。

我可以给出更清晰的实现和更容易的解释：

string phrase = "welcome to code jam"; // S
string text; getline(cin, text); // T
vector<int> ob(text.size(), 1);
int ans = 0;
for (int p = 0; p < phrase.size(); ++p) {
    ans = 0;
    for (int i = 0; i < text.size(); ++i) {
        if (text[i] == phrase[p]) ans = (ans + ob[i]) % 10000; 
        ob[i] = ans;
    }
}
cout << setfill('0') << setw(4) << ans << endl;

为了解决这个问题，如果S只有一个字符S[0]，我们可以只计算它出现的次数。

如果它只有两个字符S[0..1]，我们可以看到每次出现T[i]==S[1]都会在索引i之前增加S[0]的出现次数。

对于三个字符的答案，每次出现T[i]==S[2]类似地在索引i之前将S[0..1]的出现次数增加S[0..2]。这个数字与上一段处理T[i]时的回答值相同。

如果有四个字符，答案将是在找到第四个字符的每个索引之前增加前三个字符的出现次数，依此类推。

由于每个其他步骤都使用前几个步骤中的值，因此可以增量地解决此问题。在每一步p中，我们需要知道前一个子串S[0..p-1]在任何索引i之前出现的次数，它可以保存在与T长度相同的整数数组ob中。然后，每当我们在S[p]遇到i时，答案就会由ob[i]上升。为了为下一步准备ob，我们还将每个ob[i]更新为S[0..p]的出现次数-即当前回答值。

最后，最新的回答值(以及ob的最后一个元素)包含了整个S在整个T中出现的次数，这就是最终的答案。

请注意，它以1填充的ob开头。第一步与其他步骤不同；但计算答案的出现次数意味着每次出现时都会按1递增answer，这是所有其他步骤所做的，但它们会递增ob[i]。因此，当每个ob[i]最初都是1时，第一步将使用相同的代码像所有其他步骤一样运行。