hdu1565 方格取数(状压dp入门)

方格取数(1)

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的入门题。所谓状态压缩，就是用二进制来表示状态（0表示该位不取，1表示该位取），再将其转成十进制的数值。
例如：状态“101”，表示取第0位、第2位，不取第1位，转为十进制就是状态5。因此每个十进制数都可以代表一个唯一的状态。

针对该题，首先考虑枚举出一行中所有可能的取法或状态（不能有相邻的1），因为如果不考虑上下相邻的情况，每一行的取法或状态都是相对独立且完全相同的。
下面处理上下相邻的情况：枚举第i行所有可能的状态，枚举第i-1行所有可能的状态，两两相与，若结果为0，说明两状态之间不存在上下相邻的情况，该取法可行，反之。

AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int tai[20000];//存储所有可能出现的状态
ll dp[21][20000];//dp[i][j]第i行第j个状态的最大值
ll a[21][21];
int n;

ll cal(int row,int sta)
{
    int col=0;
    ll sum=0;
    while(sta)
    {
        int x=1<<(n-col-1);
        if(sta&x)
        {
            sta-=x;
            sum+=a[row][col];
        }
        col++;
    }
    return sum;
}

void gnt(int pos,int cnt,int last)//pos表示下一个位置，cnt表示当前状态的十进制数值，last表示上一个位置的状态
{
    if(pos==0)
    {
        tai[num++]=cnt;
        return ;
    }
    if(last)
        gnt(pos-1,cnt,0);
    else
    {
        gnt(pos-1,cnt+(1<<(pos-1)),1);
        gnt(pos-1,cnt,0);
    }
}

void init(int n)
{
    num=0;
    memset(dp,0,sizeof(dp));
    gnt(n-1,1<<(n-1),1);//1表示取，0表示不取
    gnt(n-1,0,0);
}

int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%lld",&a[i][j]);
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        init(n);
        for(int i=0; i<num; i++)
            dp[0][i]=cal(0,tai[i]);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<num;j++)//枚举第i行的状态
            {
                ll tmp=cal(i,tai[j]);
                for(int k=0;k<num;k++)//枚举第i-1行的状态
                {
                    if(tai[j]&tai[k]) continue;//上下相邻
                    dp[i][j]=max(dp[i-1][k]+tmp, dp[i][j]);
                }
            }
        }
        ll ans = 0;
        for(int j=0;j<num;j++)
            ans=max(dp[n-1][j], ans);
        printf("%lld\n",ans);
    }
    return 0;
}