SRM 474 Div2 Hard SquaresCovering

問題

２次元平面上に点が複数あり、それらの位置x[i], y[i]が与えられる。この点を複数種類の正方形で全て覆うことを考える。正方形jの幅はsides[j]で与えられる。正方形jを一つ配置するコストはcost[j]である。正方形はどの種類も無尽蔵にあるとする。全ての点を覆うコストを最小化せよ。

やりかた

practice room のOgieKakoさんのコードを参考にしました。

bitDP。dp[i]:=（点の集合iを正方形で覆うときの最小コスト）でdp。まず点集合iを一枚で覆える正方形の最小コストでdp[i]を初期化する。すると、DPは点集合iの部分集合をsubとすると

dp[i] = min(dp[i], dp[sub] + dp[i xor sub])

となる。subのループの回し方は降順でまわしていく必要がある。

たとえばi = "1101"、sub = "1100"とすると

dp[1101] = min(dp[1101], dp[1100] + dp[0001])

という感じで、部分集合のループが1100の時に下線部はすでに計算されている必要がある。昇順に列挙するとそうならない。

以下ソース。

ll dp[1 << 16];

class SquaresCovering {
public:
  int minCost(vector <int> x, vector <int> y, vector <int> cost, vector <int> sides) {
    int N = x.size();
    fill(dp, dp + (1 << N), INF);
    for(int S = 0; S < 1 << N; S++){
      ll x1 = INF, x2 = -INF, y1 = INF, y2 = -INF;
      for(int i = 0; i < N; i++)
	if(S >> i & 1){
	  x1 = min(x1, (ll)x[i]); x2 = max(x2, (ll)x[i]);
	  y1 = min(y1, (ll)y[i]); y2 = max(y2, (ll)y[i]);
	}
      
      //ここではdp[S]はSの点集合を一枚で覆える正方形の最小コストになる
      //一枚で覆えないならINF
      ll d = max(x2 - x1, y2 - y1);
      for(int i = 0; i < (int)cost.size(); i++)
	if(sides[i] >= d) dp[S] = min(dp[S], (ll)cost[i]);
      
      for(int sub = S; sub > 0; sub = (sub - 1) & S)
	dp[S] = min(dp[S], dp[sub] + dp[S ^ sub]);
    }  
    
    return dp[(1 << N) - 1];
  }
};

bitDPは苦手だ。このブログでも何回かやってみたけどまだ慣れない。

ちなみにSの部分集合の降順列挙は

for(int sub = S; sub > 0; sub = (sub - 1) & S)