Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-10-21

SRM 558 div2 easy Stamp

| 11:01

問題を見た時に、きっとDPで解くんだろうなと思いつつ、結局提出出来なかった。苦手な感じの問題なので、メモを残す。→問題

方針

スタンプを左から押していくDPを考える。DP用の配列として、dp[i][j]を用意。dp[i][j]には、「色iのスタンプをjに押した場合の最小コスト」を保存。ここで、「色iのスタンプをjに押す」とは、色iのスタンプを右端がj番目のマス目に来るように押す事と理解する。

スタンプの長さをLとすると、色iのスタンプをjに押すことが出来るのは、

  • j-L番目に別の色のスタンプを押している場合
  • j-L番目に同じ色のスタンプを押している場合
  • j-L+1番目に同じ色のスタンプを押している場合
  • (途中省略)
  • j-1番目に同じ色のスタンプを押している場合

のどれかなので、dp[i][j]にはこれらの中の最小コスト+pushCostを入れれば良い。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

int d[100];
int n;
int dp[3][100];
int cost, push;


class Stamp{
public:
  bool check(int c, int pos, int L);
  int do_dp(int L);
  int getMinimumCost(string desiredColor, int stampCost, int pushCost);



};

void debug(){
  for(int i = 0; i < 3; ++i){
    copy(dp[i], dp[i]+n, ostream_iterator<int>(cout, "\t")); cout << endl;
  }
  cout << endl;
}

bool Stamp::check(int c, int pos, int L){
  for(int i = 0; i < L; ++i){
    if(d[pos-i]==c || d[pos-i]==-1) continue;
    else return false;
  }
  return true;
}
int Stamp::do_dp(int L){
  for(int i = 0; i < 3; ++i){
    fill(dp[i], dp[i]+n, 1<<30);
    if(check(i, L-1, L)) dp[i][L-1]=push;
  }
  for(int i = L; i < n; ++i){
    for(int j = 0; j < 3; ++j){
      if(!check(j, i, L)) continue;
      for(int k = 0; k < 3; ++k){
	dp[j][i] = min(dp[k][i-L]+push, dp[j][i]);
      }
      for(int k = 1; k < L; ++k){
	dp[j][i] = min(dp[j][i-k]+push, dp[j][i]);
      }
      // cout << L << endl;
      // debug();
    }
  }
  return min(dp[0][n-1], min(dp[1][n-1], dp[2][n-1]));
}
int Stamp::getMinimumCost(string desiredColor, int stampCost, int pushCost){
  n = desiredColor.size();
  cost = stampCost;
  push = pushCost;
  for(int i = 0; i < n; ++i){
    if(desiredColor[i]=='R')d[i]=0;
    if(desiredColor[i]=='G')d[i]=1;
    if(desiredColor[i]=='B')d[i]=2;
    if(desiredColor[i]=='*')d[i]=-1;
  }
  int ret=INT_MAX;
  for(int i = 1; i<=n; ++i){
    int p = do_dp(i);
    if(p>0)ret=min(stampCost*i+p, ret);
  }
  return ret;
}
 |