TopCoder SRM612: EmoticonsDiv2

「入力済みのEmoticonsの個数」「ClipBoard上のEmoticonsの個数」で動的計画法を構成する。\(O(smiles^2)\)

public class EmoticonsDiv2 {
    static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = newValue; }

    public int printSmiles(int smiles) {
        var dp = new int[smiles + 1, smiles + 1];
        const int inf = 1 << 28;
        for (int i = 0; i <= smiles; i++) {
            for (int j = 0; j <= smiles; j++) {
                dp[i, j] = inf;
            }
        }
        dp[1, 0] = 0;
        for (int i = 0; i <= smiles; i++) {
            for (int j = 0; j <= smiles; j++) {
                if (dp[i, j] == inf) continue;
                UpdateMin(ref dp[i, i], dp[i, j] + 1);
                if (i + j <= smiles) {
                    UpdateMin(ref dp[i + j, j], dp[i, j] + 1);
                }
            }
        }
        return E.Range(0, smiles + 1).Min(s => dp[smiles, s]);
    }
}