方格取数(1)

方格取数(1)

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

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

幸亏这题数据水,最朴素的状态压缩DP就过了.

#include<stdio.h>
#include<string.h>
int N,S=0,d[25][25],s[25];
int DP[25][18000];
int state[18000];
bool legal(int x)
{
    int i;
    for (i=1;i<20;i++)
    if ((x & s[i])&&(x & s[i-1])) return false;
    return true;
}
void getstate()
{
    int i;
    for (i=0;i<25;i++) s[i]=1<<i;
    for (i=0;i<s[20];i++)
    if (legal(i))
    {
        S++;
        state[S]=i;
    }
}
int sum(int l,int st)
{
    int ans=0,i;
    if (st>=s[N]) return 0;
    for (i=0;i<N;i++)
    if (st & s[i]) ans+=d[l][i];
    return ans;
}
int main()
{
    getstate();
    while (scanf("%d",&N)!=EOF)
    {
        int i,j,k;
        if(N==0) {printf("0
");continue;}
        for (i=0;i<N;i++)
         for (j=0;j<N;j++)
             scanf("%d",&d[i][j]);
        memset(DP,0,sizeof(DP));
        for (i=1;i<=S;i++)
        {
            if (state[i]>=s[N]) break;
            DP[0][i]=sum(0,state[i]);
        }
        for (i=1;i<N;i++)
         for (j=1;j<=S;j++)
         {
             if (state[j]>=s[N]) break;
             int tmp=sum(i,state[j]);
             for (k=1;k<=S;k++)
             {
                 if (state[k]>=s[N]) break;
                 if (DP[i-1][k]>DP[i][j] && (!(state[k]&state[j]))) DP[i][j]=DP[i-1][k];
             }
             DP[i][j]+=tmp;
         }
        int Max=0;
        for (i=1;i<=S;i++)
        if (DP[N-1][i]>Max) Max=DP[N-1][i];
        printf("%d
",Max);
    }
    return 0;
}