hdu 1565格子取数(状圧dp入門)

グリッド数(1)

Problem Descriptionはn*nの格子の碁盤をあげて、各格子の中に非負の数があります.任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
Inputは複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
Outputは、各テストインスタンスについて、取得可能な最大和を出力する
Sample Input

3
75 15 21 
75 15 28 
34 70 5 

Sample Output

188

解析:この問題は状態圧縮dpの入門問題である.状態圧縮とは,状態(0はそのビットを取らず,1はそのビットを表す)をバイナリで表し,それを10進数の数値に変換することである.例えば、状態「101」は、0位、2位、1位を取らず、10進数に移行すると状態5となる.したがって、各10進数は一意の状態を表すことができます.
この問題に対して、まず、上下隣接を考慮しなければ、各行の取法または状態は相対的に独立して完全に同じであるため、1行中のすべての可能な取法または状態(隣接する1が存在しない)を挙げることを考慮する.以下、上下隣接の場合を処理する.i行目のすべての可能な状態を列挙し、i行目のすべての可能な状態を列挙し、2つの相があり、結果が0であれば、2つの状態の間に上下隣接が存在しないことを説明し、この取り方は可能であり、逆である.
ACコード

#include 
#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<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<1)),1);
        gnt(pos-1,cnt,0);
    }
}

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

int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=0; ifor(int j=0; jscanf("%lld",&a[i][j]);
        if(n==0)
        {
            printf("0
");
            continue;
        }
        init(n);
        for(int i=0; i0][i]=cal(0,tai[i]);
        for(int i=1;ifor(int j=0;j// i 
            {
                ll tmp=cal(i,tai[j]);
                for(int k=0;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;j1][j], ans);
        printf("%lld
",ans);
    }
    return 0;
}