Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-24

StripePainter

| 13:03

問題文, SRM 150

最低何回ペンキを塗りつける必要があるか。DP+メモ化で解ける問題。

224.12/500

class StripePainter {
public:
    int minStrokes(string stripes) {
        const int size = stripes.size();
        memo = vector<vector<vector<int> > >(size,vector<vector<int> >(size+1,vector<int>(128,-1)));
        return go(stripes, 0, size, '?');
    }
private:
    vector<vector<vector<int> > > memo;
    int go(const string& stripes, 
            const int left, const int size, const char color) {
        if (size <= 0) return 0;
        if (memo[left][size][color] >= 0) return memo[left][size][color];
        int best = INT_MAX;
        if (stripes[left] == color) {
            best = go(stripes, left+1, size-1, color);
        } else {
            for (int i = 1; i <= size; i++) 
                best = min(best, 1
                        + go(stripes,left+1,i-1,stripes[left])
                        + go(stripes,left+i,size-i,color));
        }
        memo[left][size][color] = best;
        return best;
    }
};