HDU-1565格子取数(1)(DP)

Description
n*nの格子の碁盤をあげて、各格子の中に非負の数があります.
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
 
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
 
Output
各テストインスタンスについて、取得可能な最大和を出力します.
 
Sample Input

     
     
     
     

      
      
      
       3
75 15 21 
75 15 28 
34 70 5 
     
     
     
     

 
Sample Output

   
   
   
   

    
    
    
     188 
 ： dp[i][j] i j ， ， ， ， 
 ， 

    
    
    
    
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1<<21;

int status[maxn], n, cnt;
int dp[2][maxn];
int ans, g[22][22];

void init() {
	cnt = 0;
	for (int i = 0; i < (1<<20); i++) {
		if (i & (i << 1))
			continue;
		else status[cnt++] = i;
	}
}

int main() {
	init();
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf("%d", &g[i][j]);
		
		if (n == 0) {
			printf("0
");
			continue;
		}

		int tot = 1 << n;
		ans = 0;
		for (int i = 0; status[i] < tot; i++) {
			dp[0][i] = 0;
			for (int j = 0; j < n; j++)
				if (status[i] & (1<<j))
					dp[0][i] += g[0][j];
			ans = max(ans, dp[0][i]);
		}

		int cur = 0;
		for (int i = 1; i < n; i++) {
			cur ^= 1; 
			for (int j = 0; status[j] < tot; j++) {
				int tmp = 0;
				dp[cur][j] = 0;
				for (int k = 0; k < n; k++) 
					if (status[j] & (1 << k))
						tmp += g[i][k];

				for (int k = 0; status[k] < tot; k++)
					if ((status[j] & status[k]) == 0)
						dp[cur][j] = max(dp[cur][j], dp[cur^1][k]+tmp);
				ans = max(ans, dp[cur][j]);
			}
		}
		
		printf("%d
", ans);
	}
	return 0;
}