SRM 499 Div 1 Easy + Medium

又一場不太難的srm呢…或許是srm 500暴風雨的前夕。沒做，其後問GG題目，的確很快想出算法，practice room passed。

250: 給了N個兔子的詢問，代表有多少兔子跟牠同一顏色，假設牠們都是說真話，求最少有多少隻兔子。

不難留意，一個詢問若得出K的話，那麼至少有K+1隻兔子。至於要得出最少答案，不難想象貪心地把最多K個兔子，其詢問都是K的「同化」一下。數式地表示就是求所有(C[K]+K)/(K+1) * (K+1)的和，當中C[K]是指有多少隻兔子的詢問是K。

550: 給了最初空的文件，你可以做以下操作。
1) 找一行插入空格。
2) 找一非空行按下Delete
3) 找一行按下Enter。此時該行會變成兩行且擁有相同的空格數量。

給定最終N行要求的空格數，求最少要多少操作。

留意三個操作疑可看作﹕1) 找一個元素+1 2)找一個元素-1 3)找一個元素分裂成兩個且保持元素數值不變

最直觀的想法就是想用類似最小生成樹的概念去「生成」要求的文件。即每次都找一個最小元素，然後按其最接近已生成的元素求最小的費用(分裂+增加)，並加入生成集之中。由此不難看出是貪心且操作2)好像沒甚麼用…而且比較難証明貪心是正確的。因此很快會想到N^3的動態規劃。假定要生成第x~y的元素，那麼就是取其中一個元素來生成，假設是x<=i<=y，然後問生成 x~i-1 和 y~i+1之間的元素最少費用是多少，然後在所有i之間取最少值。
有趣的是，細看這道題的提交，有不同的動態規劃。Petr等高手用的應該是N^4動態規劃，我想這個model是出題者本來預期的答案吧？還有N^3、N^2和種種不同的貪心。最神奇的是三行的代碼﹕

int res = lines[0] + (int)lines.size()-1;
REP(i, N-1) res += max(0, lines[i+1]-line[i]);
return res;

這種貪心，有趣得很。大意就是從左到右以lines[0]為首的連續上升元素，才需要增加用以操作1)的費用，其餘的一律不用。對的原因，我大概想的是，這個序列覆蓋了所有比它小的離散序列的增長費用，因此可以生成這個序列旳時候「順便」生成其他離散的小序列，額外費用只需要憑3)的操作，因此res最初被加上憑3)分裂成其餘N-1個元素的費用。

--
最近兩次SRM題目都很不錯，雖然550是否值得還是很有爭議，但我覺得直覺和經驗相比，總是比較難判斷。