天下一プログラマコンテスト2012 予選B C - 席が足りない

席が足りない

社員の部分集合ごとに何席必要かを覚えておいて、動的計画法。その社員が1席を共有できるなら、1席。そうでないならば、部分集合を2個に分割したそれぞれの席数の和の、最小値。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

int main()
{
    int N;
    cin>>N;

    vector<int> Ts(N), Te(N);
    for ( int i=0; i<N; i++ )
    {
        int a, b, c, d;
        scanf( "%d:%d %d:%d",&a,&b,&c,&d);
        Ts[i] = 60*a+b;
        Te[i] = 60*c+d;
    }

    vector<int> T(1<<N,N);

    for ( int bn=1; bn<=N; bn++ )
    for ( int b=0; b<(1<<N); b++ )
    if ( countbit(b)==bn )
    {
        bool ok = true;

        for ( int i=0; i<N; i++ )
        for ( int j=i+1; j<N; j++ )
        if ( (b>>i&1) && (b>>j&1) )
        {
            if ( Ts[i]<=Ts[j] && ( Te[i]>Ts[j] || Te[j]-24*60>Ts[i] ) )
                ok = false;
            if ( Ts[j]<=Ts[i] && ( Te[j]>Ts[i] || Te[i]-24*60>Ts[j] ) )
                ok = false;
        }
        
        if ( ok )
            T[b] = min(T[b],1);

        for ( int s=(b-1)&b; s>0; s=(s-1)&b )
                T[b] = min( T[b], T[s]+T[b^s] );
    }

    cout << T[(1<<N)-1] << endl;

    return 0;
}