方格取數(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，與
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<
