SRM483 Div1 Medium(500) Bribes

Bribes

賄賂の効力は指数的に減少するので、ある程度離れた人には影響しない。i番目の有権者の周囲への賄賂の配り方をjとして、i番目までの有権者が折れる最小の贈賄回数を記憶し、動的計画法。

#include <vector>
#include <algorithm>

using namespace std;

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

class Bribes{public:
int minBribes( vector <int> influence, vector <int> resistance )
{
    const int M = 2*8+1;
    int n = (int)influence.size();

    vector<int> T( 1<<M );
    for ( int i=0; i<1<<M; i++ )
        T[i] = countbit( i );

    for ( int i=0; i<n; i++ )
    {
        vector<int> P = T;
        T = vector<int>( 1<<M, n+1 );

        for ( int j=0; j<1<<M; j++ )
        {
            //  はみ出た部分は0
            if ( i <  M/2    &&  j & (1<<(M/2-i))-1  ||
                 i >= n-M/2  &&  j >> (M/2+n-i) )
                continue;

            int inf = 0;
            for ( int k=0; k<M; k++ )
                if ( j>>k & 1 )
                    inf += influence[i+k-M/2] >> abs(k-M/2);

            int p = j<<1 & (1<<M)-1;
            if ( inf >= resistance[i] )
                T[j] = min( P[p], P[p|1] ) + (j>>(M-1));
        }
    }

    int ans = *min_element( T.begin(), T.end() );
    return ans <= n ? ans : -1;
}};