HDU 2167 Pebbles

16*16*2^16

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int box[20][20];
char tmp[1000];
int sts[2][1<<17];
int main()
{
    for(;;){
        int n;
        if(gets(tmp)==0) break;
        n = (strlen(tmp)+1)/3;
        if(n == 0) continue;
        //printf("n = %d\n", n);
        for(int lx = 0;lx < n;lx++)
            box[0][lx] = 10*(tmp[lx*3]-'0')+tmp[lx*3+1]-'0';
        for(int lx = 1;lx < n;lx++)
            for(int ly = 0;ly < n;ly++)
                scanf("%d", &box[lx][ly]);
        for(int lx = 0;lx < n;lx++)
            box[n][lx] = 0;
        //if(gets(tmp)==0) break;
        memset(sts, 0, sizeof(sts));
        int now = 0;
        for(int lx = 0;lx < n;lx++){
        for(int ly = 0;ly < n;ly++){
            for(int s = 0;s < (1<<(n+1));s++){
                if(((s&1) == 0 or ly == 0) and ((s&2) == 0) and
                   ((s&4) == 0 or ly == n-1) and ((s&(1<<n)) == 0 or ly == 0)){
                    sts[1-now][(s>>1)|(1<<n)] = max(sts[1-now][(s>>1)|(1<<n)],
                                                    sts[now][s]+box[lx][ly]);
                    
                }
                sts[1-now][s>>1] = max(sts[1-now][s>>1], sts[now][s]);
                
            }
            memset(sts[now], 0,sizeof(sts[now]));
            now = 1-now;
        }}
        int mm = 0;
        for(int lx = 0;lx < (1<<n+1);lx++)
            mm = max(mm, sts[now][lx]);
        printf("%d\n", mm);
    }
    return 0;
}