#DP #Masks #SubMask #LiveArchive #Solved

3995 - Pebbles.cpp

//https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1996
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int OO = 1e4;

int getBit(int num, int indx) {
    return ((num>>indx) & 1) == 1;
}

int setBit1(int num, int indx) {
    return num | (1<<indx);
}

int setBit0(int num, int indx) {
    return num & ~(1<<indx);
}

int cntBits(int num) {
    int ret = 0;
    while(num) {
        if(num%2) {
            ret++;

        }
        num/=2;
    }
    return ret;
}

int n;
ll cache[16][1<<15+1];
int a[16][16];

ll maxPebbles(int i, int mask) {
    if(i == n)
        return 0;
    ll &ret = cache[i][mask];
    if(ret != -1)
        return ret;
    ret = 0;

    int flip = (~mask)&((1<<n)-1);
    bool isGood;
    ll sum;
    for(int tmpm = flip ;; tmpm = (tmpm - 1)&flip) {
        isGood = true;
        sum = 0;
        for(int j = 0 ; j < n; j++ ) {
            if(getBit(tmpm, j)) {
                if((j>0 && getBit(mask, j-1)) || ( j < n-1 && getBit(mask, j+1) ) || (j>0 && getBit(tmpm, j-1)) ) {
                    isGood = false;
                    break;
                }
                sum += a[i][j];
            }
        }
        if(isGood) {
            ret = max(ret, sum + maxPebbles(i+1, tmpm));
        }
        if(!tmpm)
            break;
    }

    return ret;
}

int main() {

    while(!cin.eof()) {
        string s;
        n = 0;
        while(getline(cin, s) && s != "") {
            istringstream iss(s);
            int x;
            for(int j = 0; iss>>x ; j++) {
                a[n][j] = x;
            }
            n++;
        }
        if(n==0)
            continue;
        clr(cache, -1);
        cout << maxPebbles(0, 0) << endl;

    }
    return 0;
}