SRM474 Div2 Hard(1000) SquaresCovering

TopCoder

SquaresCovering

動的計画法。2nの配列にビットが立っている点を覆う最小コストを格納。頂点を２つ選べば正方形の置き方が決まる。正方形を置く順番は任意なので、１つは最左の点を選ぶ。

#include <vector>

using namespace std;

class SquaresCovering
{
    int countbit( int n );
public:
    int minCost( vector <int> x, vector <int> y, vector <int> cost, vector <int> sides );
};

int SquaresCovering::minCost( vector <int> x, vector <int> y, vector <int> cost, vector <int> sides )
{
    int n = (int)x.size();
    int sn = (int)cost.size();

    int INF = n*cost[0];

    vector<int> C( 1<<n, INF );
    C[0] = 0;

    for ( int bit=0; bit<n; bit++ )
    {
        for ( int c=0; c<1<<n; c++ )
        if ( countbit(c) == bit  &&
             C[c] < INF )
        {
            int p1 = -1;
            for ( int i=0; i<n; i++ )
            if ( ( c & 1<<i ) == 0 ) 
                if ( p1 == -1  ||
                     x[i] < x[p1]  ||
                     x[i] == x[p1]  &&  y[i] < y[p1] )
                    p1 = i;

            for ( int p2=0; p2<n; p2++ )
            if ( ( c & 1<<p2 ) == 0  &&
                 y[p2] <= y[p1] )
            {
                for ( int s=0; s<sn; s++ )
                {
                    int t = c;
                    for ( int i=0; i<n; i++ )
                        if ( ( c & 1<<i ) == 0  &&
                             x[p1] <= x[i]  &&  x[i] <= x[p1]+sides[s]  &&
                             y[p2] <= y[i]  &&  y[i] <= y[p2]+sides[s] )
                            t |= 1<<i;

                    C[t] = min( C[t], C[c]+cost[s] );
                }
            }
        }
    }

    return C[(1<<n)-1];
}

int SquaresCovering::countbit( int n )
{
    n = ( n & 0x55555555 ) + ( n >> 1 & 0x55555555 );
    n = ( n & 0x33333333 ) + ( n >> 2 & 0x33333333 );
    n = ( n & 0x0f0f0f0f ) + ( n >> 4 & 0x0f0f0f0f );
    n = ( n & 0x00ff00ff ) + ( n >> 8 & 0x00ff00ff );
    n = ( n & 0x0000ffff ) + ( n >>16 & 0x0000ffff );
    return n;
}