正方形格通路(1)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4702 Accepted Submission(s): 1782

Problem Description

给你一个n*n的格子的棋盘，每一个格子里面有一个非负数。

从中取出若干个数。使得随意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻。而且取出的数的和最大。

Input

包含多个測试实例，每一个測试实例包含一个整数n 和n*n个非负数(n<=20)

Output

对于每一个測试实例。输出可能取得的最大的和

Sample Input

      3 75 15 21 75 15 28 34 70 5 

Sample Output

188

入门压缩dp，与

类似。

用dp[i][j]表示前i行。第i行选第j种状态时的最优解，

首先找出全部本行不冲突的状态（即这一行中没有相邻的情况），存入state数组

计算出第i行取第j种状态时可得到的数值stn[i][j]

那么dp[i][j]=max{dp[i][j],dp[i-1][k]+stn[i][j]} (k表示第i-1行取第k种状态

终于答案即为dp[n][j]中的最大值。

代码：

#include
    
     #include
     
      #include
      
       using namespace std;const int hpn=18000;int state[hpn],stn[25][hpn],dp[25][hpn];//dp[i][j]:前i行，第i行选第j种状态时的最优解int mst,map[25][25];//第i行选第j种状态时的值inline int bet(int x,int y){	if(x>y)	return x;	return y;}void find_all_state(int n){	memset(state,0,sizeof(state));	mst=0;//最多有多少种状态	int lin=(1<
       
        >n)	{		if(n==0)		{			cout<<0<

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4874332.html，如需转载请自行联系原作者