从谷歌编程挑战赛解决“欢迎来到编程挑战赛” 2009

我试图解决以下代码拥堵问题，我已经取得了一些进展，但对于少数情况下我的代码给出错误的输出.. Welcome to Code jam 从谷歌编程挑战赛解决“欢迎来到编程挑战赛” 2009

所以我迷迷糊糊来自俄罗斯的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

有人可以解释什么在两个循环发生？

谢谢。

来源

2012-03-17 ashishsony

哦，男孩，这里有一个提示：*不要试图从这段代码学习*。 – 2012-03-17 10:54:43

如何在这里发布问题 – 2012-03-17 10:55:16

休息片REM。其中一位非常优秀的程序员非常年轻。你可以看到你仍然有影响，没有被遗忘。 – 2012-03-17 11:01:43

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

他有二维数组，你需要了解它的语义。事实是，dp[i][j]计算他可以使用输入字符串中第i个索引的所有字母获得第一个字母welcome to code jam的子序列的方式的数量。这两个索引都是基于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].

你特别询问计算基于新的动态值的环已经计算好的。

来源

2012-03-17 11:10:58

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

我怀疑说“他在做动态规划”，如果你不学习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]由S[0]出现的次数指数i之前增加了答案。

对于三个字符S[0..2]每次出现T[i]==S[2]同样增加回答S[0..1]出现在索引i之前的出现次数。该数字与前一段落处理的答案值相同T[i]。

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

由于每隔一个步骤使用先前的值，因此可以逐步解决。在每一步p我们需要的任何索引i，它可以保存在整数相同长度的ob的阵列T.那么答案上升由ob[i]每当我们在i遇到S[p]之前知道以前的子S[0..p-1]的出现次数。并且为了准备ob进行下一步骤，我们还将每个ob[i]更新为S[0..p]的出现次数，即，将其更新为当前应答值。

最后的最后答案值（和最后一个元素ob）包含整个S整个T的出现次数，这就是最终答案。

请注意，它始于ob填充1。第一步与其他步骤不同;但是统计S[0]的出现次数意味着在每次出现时增加回答1，这是所有其他步骤所做的，除了它们增加ob[i]。因此，当每个ob[i]最初是1时，第一步将像所有其他人一样运行，使用相同的代码。

来源

2012-06-29 17:58:11 hamstergene

从谷歌编程挑战赛解决“欢迎来到编程挑战赛” 2009

回答

相关问题