Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-10-20

SRM558 275

| 00:57 | はてなブックマーク -  SRM558 275 - cafelier@SRM

重ね塗りを考慮するのややこしいので、重ね塗りを考えないのが多分一番良い解き方だと思う。

「長さピッタリ L のスタンプ。1回押すのに pushCost。色があってれば重ね塗りしても良い」の代わりに「長さ L 以上の可変長スタンプ。長さ W にして1回押すのに ((W+L-1)/L)*pushCost。重ね塗り禁止」と考える。

(W+L-1)/L というのは、(L,2L]なら2回、(2L,3L]なら3回、…というあれです。

class Stamp { public:
   int getMinimumCost(string desiredColor, int stampCost, int pushCost)
   {
      const int N = desiredColor.size();

      int best = 0x7fffffff;
      for(int L=1; L<=N; ++L) {
         vector<int> dp(N+1, 999);
         dp[0] = 0;
         for(int e=1; e<=N; ++e) {
            // desiredColor[0,e) を塗るのに何回で塗れるか。
            set<char> colors;
            for(int s=e-1; s>=0; --s) {
               if(desiredColor[s] != '*')
                  colors.insert(desiredColor[s]);
               if(colors.size()<=1 && e-s>=L) {
                  int nPush = (e-s+L-1)/L;
                  // desiredColor[0,s) を巧く塗って desiredColor[s,e) を可変スタンプ1発で塗る
                  dp[e] = min(dp[e], dp[s]+nPush);
               }
            }
         }
         best = min(best, L*stampCost + dp[N]*pushCost);
      }
      return best;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20121020
 | 

presented by cafelier/k.inaba under CC0