從谷歌編程挑戰賽解決「歡迎來到編程挑戰賽」 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

回答

相關問題