cafelier@SRM

SRM558 275

あとで | 00:57 |

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

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

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

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) を可変スタンプ１発で塗る
                  dp[e] = min(dp[e], dp[s]+nPush);
               }
            }
         }
         best = min(best, L*stampCost + dp[N]*pushCost);
      }
      return best;
   }
};