/****** 题意:从一个矩阵中选出一些数,选出的数不能相邻,求能选出的最大的和; 思路:状压DP 也可以用什么流做,不过现在不懂图论 *******/ #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define INF 0xfffffff using namespace std; int dp[20][17777], a[20][20], cnt, s[1<<20], num1[20][17777], n; int num(int i, int k) { int ans = 0, j; for(j = 0; j < n; j++) if(k & (1 << j)) ans += a[i][j]; return ans; } bool can(int k) { if(k&(k<<1)) return false; return true; } void DP() { int i,j,k; memset(dp,0,sizeof(dp)); for(j=0;j<cnt;j++) dp[0][j]=num1[0][j]; for(i=1;i<n;i++) { for(j=0;j<cnt;j++) { for(k=0;k<cnt;k++) if((s[k]&s[j])==0) { dp[i][j]=max(dp[i][j],dp[i-1][k]+num1[i][j]); } } } } int main() { //freopen("input.txt","r",stdin); //freopen("outputh.txt","w",stdout); while(scanf("%d", &n) != EOF) { if(n == 0) { puts("0"); continue; } int i,j,k; cnt=0; for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d", &a[i][j]); for(k=0;k<(1<<n);k++) if(can(k)) { s[cnt]=k; cnt++; } for(i = 0; i < n; i++) for(k=0;k<cnt;k++) num1[i][k]=num(i,s[k]); DP(); int ans=0; for(j=0;j<cnt;j++) ans=max(ans,dp[n-1][j]); printf("%d\n", ans); } return 0; }