A题简单DP,不过判断一段的颜色是否相同要用点小技巧(见代码)

const int mx = 55;

int a[mx], dp[mx];

class Stamp
{
    public:
        int getMinimumCost(string desiredColor, int stampCost, int pushCost)
        {
            int i, j, len, seg, N = desiredColor.size(), color, res = inf;
            char c;
            For(i, N) /// 嗯,神一样的技巧(思想来自Unix)
         {
                c = desiredColor[i];
                if (c == 'R') a[i] = 1;
                else if (c == 'G') a[i] = 2;
                else if (c == 'B') a[i] = 4;
                else a[i] = 7; // '*'
         }
            Forr(len, 1, N + 1)
            {
                mem(dp, 0x3f);
                dp[0] = 0;
                For(i, N)
                {
                    //with each position i, we try to paint
                 //until the furthest position j as long as we can use just 1 color
                 color = 7;
                    Forr(j, i, N)
                    {
                        color &= a[j];
                        if (color == 0) break;
                        seg = j - i + 1;
                        if (seg >= len && dp[i] != inf)
                            dp[j + 1] = min(dp[j + 1], dp[i] + ((seg + len - 1) / len) * pushCost);
                    }
                }
                if (dp[N] != inf) res = min(res, dp[N] + stampCost * len);
            }
            return res;
        }
};

Comments

comments powered by Disqus