格子取数(1)(HDU-1565)

1739 ワード

# HDU ダイナミックプランニング DP

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
タイトル中のn<=20であるが,各行の条件を満たす状態を列挙するだけであり,実際にn=20となると合法状態は16となるため,実際にはn<=16となる.
前i行のi行目j種の状態をdp[i][j]で表したときの最大和は、i行目j個目の状態をsum[i][j]で表した値の総和であり、dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[i][j])があり、2行の状態が0であれば状態遷移が可能である

Source Program

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 16
#define MOD 10007
#define E 1e-6
#define LL long long
using namespace std;
int n;
int a[21][21];
int dp[21][1<>i)&1)
            res+=a[k][n-1-i];
    return res;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i>1)))// 
                sta[len++]=i;

        for(int i=0;i

kafka送信超大メッセージ設定

剣指offer面接問題9——階段を跳ぶ(非ロネ数列)