程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1565 狀壓dp

HDU 1565 狀壓dp

編輯：C++入門知識

HDU 1565 狀壓dp

從第一行到開始，一行一行進行考慮

方格取數(1)

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

Problem Description 給你一個n*n的格子的棋盤，每個格子裡面有一個非負數。
從中取出若干個數，使得任意的兩個數所在的格子沒有公共邊，就是說所取的數所在的2個格子不能相鄰，並且取出的數的和最大。
Input 包括多個測試實例，每個測試實例包括一個整數n 和n*n個非負數(n<=20)
Output 對於每個測試實例，輸出可能取得的最大的和
Sample Input

Sample Output

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 18005
int dp[22][MAXN],V[22][22],state[MAXN];

int Max(int a,int b){
    return a>b?a:b;
}

bool canuse(int x){//判斷哪些位置是可以的
    bool f = false;
    while(x){
        if(x%2 && f){
            return false;
        }
        if(x%2){
            f = true;
        }
        else{
            f = false;
        }
        x>>=1;
    }
    return true;
}

bool legal(int x,int y){//列之間的關系
    if(x&y){
        return false;
    }
    else{
        return true;
    }
}

int main(){
    int i,j,t,x,num,ans,n;

    while(~scanf("%d",&n)){
        num = 0;
        for(i=0;i<(1<