HDU1565-方格取数(1)

方格取数(1)

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

Problem Description

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

Sample Output

188

Author

ailyanlu

个人第一道状态压缩DP

#include<stdio.h>
#include<string.h>
int dp[2][1<<20];   //这题要用滚动数组，否则MLE
int tmp[1<<20],sum;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,i,j,k,index;
int a[21][21];
while(scanf("%d",&n)!=EOF)
{
  index=0;
  for(i=1;i<=n;i++)
  {
   for(j=0;j<n;j++)
    scanf("%d",&a[i][j]);
  }
  for(i=0;i<(1<<n);i++)
  {
   if( !((i<<1) & i) && !((i>>1) & i) )
    tmp[index++]=i;
  }
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++)
  {
   for(j=0;j<index;j++)
   {
    sum=0;
    for(k=0;k<n;k++)
    {
     if( ((1<<k) & tmp[j]) )
     {
      sum+=a[i][k];
     }
    }
    for(k=0;k<index;k++)
    {
     if( (tmp[j] & tmp[k]) == 0 )
      dp[1][tmp[j]]=max(dp[1][tmp[j]],dp[0][tmp[k]]+sum);
    }
   }
   for(j=0;j<index;j++)
   {
    dp[0][tmp[j]]=dp[1][tmp[j]];
    dp[1][tmp[j]]=0;
   }
  }
  int MAX=dp[0][0];
  for(i=0;i<index;i++)
  {
   if(MAX<dp[0][tmp[i]])
    MAX=dp[0][tmp[i]];
  }
  printf("%d ",MAX);
}
return 0;
}