方格取数(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

Sample Output

入门压缩dp，与

Poj - 3254 Corn Fields

类似。

用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<

Hdu-1565 方格取数(1) （状态压缩dp入门题

方格取数(1)

Poj - 3254 Corn Fields