HDU 1565 方格取数(1)

/*

dp+状态压缩和炮兵阵地类似

*/

#include<stdio.h>
#include<string.h>
#define Max(a,b) a>b?a:b
int dp[25][20000],s[20000],len,Map[25][25],n;
int check(int m)
{
    if(m&(m<<1))
        return 0;
    return 1;
}
void Inint()
{
    len=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(check(i))
            s[len++]=i;
    }
}
int Count(int id,int m)
{
    int d=n-1,sum=0;
    while(m>0)
    {
        if(m&1)
            sum+=Map[id][d];
        d--;
        m>>=1;
    }
    return sum;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        memset(Map,0,sizeof(Map));
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&Map[i][j]);
        Inint();
        for(int i=0;i<len;i++)
            dp[0][i]=Count(0,s[i]);
       for(int r=1;r<n;r++)
       {
           for(int i=0;i<len;i++)
                for(int j=0;j<len;j++)
                    if((s[i]&s[j])==0)
                        dp[r][i]=Max(dp[r][i],dp[r-1][j]+Count(r,s[i]));
       }
       int ans=0;
       for(int i=0;i<len;i++)
        if(dp[n-1][i]>ans)
            ans=dp[n-1][i];
       printf("%d\n",ans);
    }
    return 0;
}

HDU 1565 方格取数(1)

原文：http://blog.csdn.net/u013491149/article/details/43014555