SRM558 DIV1 275 Stamp

スタンプの長さ（L = 1 〜 desiredColor.size()）と、最初に何色で塗るか（3通り）を全通り試す。

int n=desiredColor.size();
int res=inf;
for(int L=1;L<=n;++L) {
    for(int c=1;c<=3;++c) { // R=1, G=2, B=3
        res=min(res, L*stampCost + (長さL、最初にcで塗ったときの最小push回数)*pushCost);
    }
}

最小push回数を求める部分は、
・重ね塗りできるのは同じ色だけ
・まだ塗っていないところは何色でもいい
・ボードからスタンプがはみ出してはいけない
というルールに気をつけて左から右に塗っていく感じでメモ化全探索。

#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;

int a[51],n;
ll memo[4][51];
const ll inf=(1LL<<40);
class Stamp {
    // 長さLのスタンプでk〜k+L-1番目のセルを色cで塗った場合、
    // k番目以降をdesiredColorに合わせるための最小push回数
    ll func(int L, int c, int k)
    {
        // はみ出しちゃダメ
        if (k+L>n) return inf;
        // desiredColorじゃない色で塗っちゃダメ
        rep(i,L) if (a[k+i] && a[k+i]!=c) return inf;
        // 最後まで塗れたらOK
        if (k+L==n) return 1;

        ll& res=memo[c][k];
        if (res) return res;
        res=inf;
        // [k+1,k+L)の範囲はcと同じ色でしか塗れない
        REP(i,1,L) res=min(res,func(L,c,k+i)+1);
        // まだ塗っていないセルは何色で塗ってもいい
        REP(i,1,4) res=min(res,func(L,i,k+L)+1);
        return res;
    }
    public:
    int getMinimumCost(string desiredColor, int stampCost, int pushCost)
    {
        ll res=inf;
        n=desiredColor.size();
        rep(i,n)switch(desiredColor[i]){
            case 'R': a[i]=1; break;
            case 'G': a[i]=2; break;
            case 'B': a[i]=3; break;
            default: a[i]=0;
        }
        // スタンプの長さ、最初に何色で塗るかを全探索
        REP(L,1,n+1) REP(c,1,4) {
            memset(memo,0,sizeof(memo));
            res=min(res,L*stampCost+func(L,c,0)*pushCost);
        }
        return int(res);
    }
};