首页 > 代码库 > HDU 1565 状压dp

HDU 1565 状压dp

2024-07-30 19:59:09   225人阅读

从第一行到开始，一行一行进行考虑

方格取数(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
3
75 15 21 
75 15 28 
34 70 5
 

Sample Output
188
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <limits.h>
#include <ctype.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <set>
#include <map>
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<<n);i++){
            if(canuse(i)){
                state[++num] = i;
            }
        }
        for(i=1;i<=n;i++){
            for(j=0;j<n;j++){
                scanf("%d",&V[i][j]);
            }
        }
        memset(dp,0,sizeof(dp));
        for(t=1;t<=n;t++){
            for(i=1;i<=num;i++){
                int d = 0;
                for(x=0;x<n;x++){
                    if(state[i]&(1<<x)){
                        d+=V[t][x];
                    }
                }
                for(j=1;j<=num;j++){
                    if(legal(state[i],state[j])){
                        dp[t][i] = Max(dp[t][i],d+dp[t-1][j]);
                    }
                }
            }
        }
        ans = 0;
        for(i=1;i<=num;i++){
            ans = Max(ans,dp[n][i]);
        }
        printf("%d\n",ans);
    }

    return 0;
}


HDU 1565 状压dp


联系
我们