SRM 554 Div2

250 TheBrickTowerEasyDivTwo

並べるだけ

class TheBrickTowerEasyDivTwo {
public:
  int find(int redCount, int redHeight, int blueCount, int blueHeight) {
    int now_h = 0;
    int C[2] = {blueCount,redCount};
    int H[2] = {blueHeight,redHeight};
    memset(tower,0,sizeof(tower));    
    bool col = true;//red
    while(true){
      if(C[col] > 0){
	now_h += H[col];
	tower[now_h] = true;
	C[col]--;
      }else{
	break;
      }
      col = !col;
    }
    col = false; //blue
    now_h = 0;
    C[0] = blueCount,C[1] = redCount;
    H[0] = blueHeight,H[1] = redHeight;
    while(true){
      if(C[col] > 0){
    	now_h += H[col];
    	tower[now_h] = true;
    	C[col]--;
      }else{
    	break;
      }
      col = !col;
    }
    int res = 0;
    rep(i,10000)
      if(tower[i])
	res++;
    return res;
  }
};

500 TheBrickTowerMediumDivTwo

n!とかでいけるので、順列生成する。
next_permutation使ったら460とかで提出できた

class TheBrickTowerMediumDivTwo {
public:
  vector <int> find(vector <int> heights) {
    vector<int>nums;
    rep(i,heights.size()) nums.pb(i);
    int min_i = INF;
    vector<int>id;
    do{
      int sum = 0;
      rep(i,nums.size() - 1){
	int dist = max(heights[nums[i]],heights[nums[i + 1]]);
	sum += dist;
      }
      if(sum < min_i){
	min_i = sum;
	id = nums;
      }
    }while(next_permutation(all(nums)));
    return id;
  }
};

(おまけ)
next_permutationを使用しないバージョン

int N;

struct E{
  vector<int>nums;
  int dist;
  E(){dist = INF;};
  E(vector<int>n,int d){
    nums = n,dist = d;
  }
};
vector<int>nums;
vector<int>heights;
class TheBrickTowerMediumDivTwo {
public:
  int calc_d(vector<int>n){
    int res = 0;
    rep(i,n.size() - 1){
      int dist = max(heights[n[i]],heights[n[i + 1]]);
      res += dist;
    }
    return res;
  }
  E dfs(int n,int x){
    nums.pb(x);
    if(n < N - 1){
      E mn;
      for(int i = 0; i < N; i++){
	E tmp;
	if(std::find(all(nums),i) == nums.end()){
	  tmp = dfs(n + 1,i);
	  if(mn.dist > tmp.dist){
	    mn.dist = tmp.dist;
	    mn.nums = tmp.nums;
	  }
	}
      }
      nums.pop_back();
      return mn;
    }
    int tmp_d = calc_d(nums);
    E ret = (E){nums,tmp_d};
    nums.pop_back();
    return ret;
  }
  vector <int> find(vector <int> h) {
    heights = h;
    N = heights.size();
    E res;
    for(int i = 0; i < N; i++){
      E tmp = dfs(0,i);
      if(res.dist > tmp.dist){
      	res.dist = tmp.dist;
      	res.nums = tmp.nums;
      }
    }
    return res.nums;
  }
};