方格取数之状态压缩

3/8/2017来源:ASP.NET技巧人气:1299

方格取数(1)

Time Limit: 10000/5000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8493    Accepted Submission(s): 3226 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

 

Author
ailyanlu
 

Source
Happy 2007

 

Recommend
8600

题目大意:取不能有临边的点,求最大和

分析:把每一列转化为2进制每一位,1表示这个格子取,0为不取,通过二进制得到的整数值表示一个状态。

这边判断没有临边的方法即x&y==0同时x与y的二进制也没有相邻的1。即x&(x<<1)==0

用dp[i][j]表示第i行状态为j的最大和,那么它是由前面的i-1行的状态过来的。

方程为:dp[i][j]=max{dp[i][j],dp[i-1][k]+sum[j]}其中sum[j]表示在i行的状态为j取到数的和

 最后结果为max{dp[n][i]} i为状态

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int b[1000];
int a[22][22];
int dp[22][19000];
int main()
{
    int n;
    while(scanf("%d",&n)!=-1)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        memset(dp,0,sizeof(dp));
        int maxn=1<<n;
        int p=0;
        for(int i=0;i<maxn;i++)
        {
            if((i&i<<1)==0)
            {
                b[p++]=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<p;j++)
            {
                int sum=0;
                for(int k=0;k<n;k++)//计算这个状态下的值
                {
                    if((b[j]&(1<<k)))//只要这个状态中第k+1位为1则取当前的值
                    {
                        sum+=a[i][k+1];
                    }
                }
                dp[i][j]=sum;
                for(int ha=0;ha<p;ha++)//和i-1行的各种状态比较,找出最大的
                {
                    if((b[j]&b[ha])==0)
                    dp[i][j]=max(dp[i-1][ha]+sum,dp[i][j]);
                }
            }
        }
        int ma=-1;
        for(int i=0;i<p;i++)
        {
            ma=max(ma,dp[n][i]);
        }
        printf("%d\n",ma);
    }
}