SRM478 Div1 Medium(500) KiwiJuice - kusano

ボトルの集合Bから得られるジュースの量の組み合わせは、ジュースを寄せ集めるか、Bを2つに分けてそれぞれ再帰的にジュースを動かすかのどちらか。立っているビットの部分集合の列挙は↓のようにできるらしい。すげー。

#include <vector>

using namespace std;

class KiwiJuice
{
public:
    int theProfit( int C, vector <int> bottles, vector <int> prices );
};

int 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;
}

int KiwiJuice::theProfit( int C, vector <int> bottles, vector <int> prices )
{
    int n = (int)bottles.size();

    //  立っているビットのボトルを用いて得られる最大金額
    vector<int> p(1<<n);

    for ( int i=1; i<=n; i++ )
    {
        for ( int j=0; j<1<<n; j++ )
        if ( countbit(j) == i )
        {
            int sum = 0;
            for ( int k=0; k<n; k++ )
            if ( ( j & 1<<k ) != 0 )
                sum += bottles[k];

            p[j] = sum/C*prices[C]
                 + (C*i-sum)/C*prices[0]
                 + ( sum%C>0 ? prices[sum%C] : 0 );

            for ( int k=(j-1)&j; k>0; k=(k-1)&j )
                p[j] = max( p[j], p[k]+p[j^k] );
        }
    }

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