Div2 500 - SquaresCovering

問題

与えられた座標を覆うように正方形を配置する．正方形それぞれにコストがかかるので，その総和の最小値はいくらになるか？

考え方

点の数が高々 16 個なので，どの点がまだカバーされてないかをビットで表した DP で大丈夫だと思う．点を x 座標なりで適宜ソートしておくと計算しやすい．正方形の位置については，適当に移動させれば覆う点自体は変わらずに左辺と上辺に点があるように変更できるので，そういう場合だけ考慮すればいい．

コード

#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int, int> Queue; // cost, remained square
typedef pair<int, int> Point; // x, y
const int INF = 0x7fffffff;

class SquaresCovering
{
  set<Queue> q;
  vector<Point> point;
  vector<int> pay;

  void push(int rem, int cost)
  {
    if( pay[rem] > cost ) {
      pay[rem] = cost;
      q.insert(Queue(cost, rem));
    }
  }
public:
  int minCost(vector<int> x, vector<int> y, vector<int> cost, vector<int> sides)
  {
    const int Ns = cost.size(); // # of square
    const int Np = x.size();    // # of points
    const int Nf = 1 << Np;     // # of flag pattern

    for( int i = 0 ; i < Np ; ++i ) point.push_back(Point(x[i], y[i]));
    sort(point.begin(), point.end());

    pay.resize(Nf, INF);
    q.insert(Queue(0, Nf - 1));
    pay[Nf - 1] = 0;
    while( !q.empty() ) {
      int cst = q.begin()->first, flg = q.begin()->second, id;
      if( flg == 0 ) break;
      q.erase(q.begin());
      // Check left-most point
      for( id = 0 ; id < Np ; ++id ) if( (1 << id) & flg ) break;

      for( int i = 0 ; i < Ns ; ++i ) { // Square selection
        int size  = sides[i], ncost = cst + cost[i];
        int right = point[id].first + size;
        for( int j = id ; j < Np ; ++j ) { // To detect top position
          if( (flg & (1 << j)) == 0 ) continue;
          if( right < point[j].first ) continue;
          if( point[j].second < point[id].second || point[id].second + size < point[j].second ) continue;
          const int top = point[j].second, bottom = top - size;
          int rem = flg;
          for( int k = id ; k < Np ; ++k ) { // Check each point is in square
            if( (rem & (1 << k)) == 0 ) continue;
            if( right < point[k].first ) continue;
            if( bottom <= point[k].second && point[k].second <= top ) rem ^= (1 << k);
          }
          push(rem, ncost);
        }
      }
    }
    return pay[0];
  }
};