mayoko’s diary

プロコンとかいろいろ。

SRM 558 div1 easy Stamp

問題

TopCoder Statistics - Problem Statement

一列に並んだ N マスを指定された色に塗りつぶしたい(色の指定のない箇所もあるが, 何らかの色を塗る必要はある)。そのために, 以下の 2 つの操作をする。

  • まず, 長さ L のスタンプを作る。これには L * stampCost だけコストがかかる。
  • 上で作ったスタンプを使って, 色を塗る。このとき, すでに塗っている箇所を別の色で塗りつぶす操作は許されない。一回塗るごとに pushCost かかる。

最小のコストはいくらか。

解法

長さ L のスタンプを使う際, 目標のセルを作るために必要なスタンプを押す最小数を求められれば, この L を全探索するだけで解が得られます。

最小数の求め方ですが,

dp[i][c] = ([0, i+L) まで塗っていて, (つまり 地点 i でスタンプを押したのが一番最後) この最後の塗りは色 c で行っている際の, スタンプを押す最小回数) というのを dp すれば良いです。

i の次に [i+1, i+L) の区間から次の塗る色を選択する場合は, すでにその区間は c で塗られているので, 同じ色 c である必要があります。また, 次に塗る範囲を [j, j+L) とすると, その区間の色はすべて '*' か 指定した色でなければなりません。

この条件を満たしていたら遷移する, ということをやればできます。

const int INF = 1000;
const string RGB = "RGB";
int dp[55][3];

int calc(int L, string dc) {
    int n = dc.size();
    for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++)
        dp[i][j] = INF;
    for (int i = 0; i < 3; i++) {
        bool ng = false;
        for (int j = 0; j < L; j++) {
            if (dc[j] != '*' && dc[j] != RGB[i]) ng = true;
        }
        if (!ng) dp[0][i] = 1;
    }
    for (int i = 0; i+L <= n; i++) for (int j = 0; j < 3; j++) {
        if (dp[i][j] >= INF) continue;
        for (int k = i+1; k+L <= n && k <= i+L; k++) {
            for (int c = 0; c < 3; c++) {
                if (k < i+L && c != j) continue;
                bool ng = false;
                for (int l = k; l < k+L; l++) {
                    if (dc[l] != '*' && dc[l] != RGB[c]) ng = true;
                }
                if (!ng) dp[k][c] = min(dp[k][c], 1+dp[i][j]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 3; i++)
        ans = min(ans, dp[n-L][i]);
    return ans;
}

class Stamp {
public:
    int getMinimumCost(string desiredColor, int stampCost, int pushCost) {
        int n = desiredColor.size();
        int ans = 1e9;
        for (int i = 1; i <= n; i++) {
            ans = min(ans, calc(i, desiredColor) * pushCost + i*stampCost);
        }
        return ans;
    }
};