Hatena::Grouptopcoder

tsubosakaの日記

2012-10-20

SRM 558 275

19:40

重ね塗りとかを考えるのが、結構面倒で時間内に解けなかったので

http://topcoder.g.hatena.ne.jp/cafelier/20121020/1350662225

みたいにすれば良かったなと思った


import java.util.*;

public class Stamp {
  
  int getMinimum(int[] arr){
    int mi = 0;
    for(int i = 1 ; i < arr.length ; ++i)
      if(arr[i] < arr[mi])
        mi = i;
    return arr[mi];
  }

  boolean canColor(int index , int L , char c , char arr[]){
    for(int i = index ; i < index + L ; ++i){
      if(arr[i] == '*' || arr[i] == c)continue;
      return false;
    }
    return true;
  }
  // [0,current)までが塗られている状況で[current,current+L)をcolorで塗るための最小コストを返す
  int getMinCost(int[][] dp, int L , int current , int color){
    int min = 10000;
    if(current - L >= 0){ //[current-L, current)までが塗られている
      min = getMinimum(dp[current - L]) + 1;
    }
    for (int j = 0; j < current; ++j) {
      if (j + L < current)
        continue;
      min = Math.min(dp[j][color] + 1, min);
    }
    return min;
  }
    
  int minPush(char[] desiredColor, int L) {
    if(L == 1)return desiredColor.length;
    int len = desiredColor.length;
    char[] colors = {'R' , 'G' , 'B'};
    int dp[][] = new int[len][3];
    for (int i = 0; i < len; ++i) {
      Arrays.fill(dp[i], 10000);
    }
    for(int c = 0 ; c < 3 ; ++c){
      if(canColor(0, L, colors[c], desiredColor)){
        dp[0][c] = 1;
      }
    }
    for (int i = 1; i + L <= len; ++i) {
      for(int c = 0; c < 3 ; ++c){
        if(canColor(i, L, colors[c], desiredColor)){
          dp[i][c] = getMinCost(dp, L, i, c);
        }
      }
    }
    return getMinimum(dp[len - L]);
  }

  public int getMinimumCost(String desiredColor, int stampCost, int pushCost) {
    int res = Integer.MAX_VALUE;
    int L = desiredColor.length();
    for (int l = 1; l <= L; ++l) {
      int sc = l * stampCost;
      int pc = minPush(desiredColor.toCharArray(), l) * pushCost;
      res = Math.min(res, sc + pc);
    }
    return res;
  }
}