学步园

//状态压缩DP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int N=17, M=1600;
int map[N][N], p[N], val[M][N], dp[N][M], sum[N][M];
vector<int> mat[M];
int n,num,ans;

void Make()
{
    memset(p,0,sizeof(p));
    int i,j,m,tmp,x;
    num=0;
    m=(1<<n)-1;
    for(i=0;i<=m;i++)
    {
        tmp=n; x=i;
        while(x){
            p[tmp--]=x%2;
            x/=2;
        }

        for(j=2;j<=n;j++)
            if(p[j] && p[j-1]) break;
        if(j==n+1)
        {
            for(j=1;j<=n;j++)
                val[num][j]=p[j];
            num++;
        }
    }
}

bool check(int *a, int *b)
{
	for(int i=1;i<=n;i++)
		if(a[i] && (b[i-1] || b[i] || b[i+1])) return 0;
	return 1;
}

void init()
{
	int i,j,k;
	memset(sum,0,sizeof(sum));
	for(i=0;i<num;i++)
		for(j=i+1;j<num;j++)
			if( check(val[i], val[j]) )
			{
				mat[i].push_back(j);
				mat[j].push_back(i);
			}
	for(i=1;i<=n;i++)
		for(j=0;j<num;j++)
			for(k=1;k<=n;k++) sum[i][j]+=val[j][k]*map[i][k];
}

void solve()
{
	int i,j,k,cur;
	memset(dp,0,sizeof(dp));
	for(i=1;i<=n;i++)
		for(j=0;j<num;j++)
		{
			int m=mat[j].size();
			for(k=0;k<m;k++)
			{
				cur=mat[j][k];
				dp[i][j]=max(dp[i][j], dp[i-1][cur]+sum[i][j]);
			}
		}
	ans=0;
	for(i=0;i<num;i++) ans=max(ans,dp[n][i]);
}

int main()
{
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    char s[100];
    int tmp,i,j,len,m,k=1;

    while(gets(s)!=NULL)
    {
        len=strlen(s);
        n=(len+1)/3;
        for(i=0,j=1;i<len;i+=3)
            map[1][j++]=10*(s[i]-'0')+s[i+1]-'0';

        for(k=2;k<=n;k++){
            gets(s);
            for(i=0,j=1;i<len;i+=3)
                map[k][j++]=10*(s[i]-'0')+s[i+1]-'0';
        }
        getchar();

        Make();
        init();
        solve();
        printf("%d\n",ans);
    }
    return 0;
}