HDU 1565 체크 수 (1) (상 압 DP)

체크 개수 (1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8141 Accepted Submission(s): 3073
Problem Description n * n 칸 의 바둑판 을 드 리 겠 습 니 다. 칸 마다 마이너스 가 있 습 니 다.그 중에서 몇 개의 수 를 꺼 내 서 임의의 두 개의 수가 있 는 칸 이 공공 변 이 없 게 한다. 즉, 취 하 는 수가 있 는 두 개의 칸 이 서로 인접 하지 못 하고 취 하 는 수의 합 이 가장 크다 는 것 이다.
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 | We have carefully selected several similar problems for you: 1569 1532 3338 1533 1733
상 압 DP, 우선 dfs 로 현재 줄 의 모든 상 태 를 생 성, nowstatus 는 바 이 너 리 의 모든 방안 을 저장 합 니 다. nowsum 은 모든 방안 (현재 줄 의 합) 을 저장 합 니 다.pre_status 는 이전 줄 의 방안 을 저장 합 니 다. 현재 줄 의 선택 은 이전 줄 과 관련 이 있 기 때 문 입 니 다. presum 은 앞의 모든 줄 의 실행 가능 한 방안 의 합 을 저장 합 니 다.

#include "cstring"
#include "cstdio"
#include "iostream"
#include "string.h"
#include "algorithm"
#include "cmath"
using namespace std;
int mmap[25][25];
int n;
int now_status[20000],now_sum[20000],nowid,preid,dp[20000],pre_status[20000],pre_sum[20000];
void dfs(int row,int column,int status,int sum)
{
    if(column>=n)
    {
        now_status[++nowid]=status;
        now_sum[nowid]=sum;
        return;
    }
    dfs(row,column+2,status|1<1,status,sum);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(mmap,0,sizeof(mmap));
        for(int i=0;ifor(int j=0;jscanf("%d",&mmap[i][j]);
        memset(pre_status,0,sizeof(pre_status));
        memset(now_status,0,sizeof(now_status));
        memset(now_sum,0,sizeof(now_sum));
        memset(pre_sum,0,sizeof(pre_sum));
        memset(dp,0,sizeof(dp));
        preid=0;
        for(int k=0;k1;
            dfs(k,0,0,0);
            memset(dp,0,sizeof(dp));
            for(int i=0;i<=nowid;i++)
            {
                for(int j=0;j<=preid;j++)
                {
                    if(now_status[i]&pre_status[j])continue;
                    dp[i]=max(dp[i],pre_sum[j]+now_sum[i]);
                }
            }
            for(int i=0;i<=nowid;i++)
            {
                pre_sum[i]=dp[i];
                pre_status[i]=now_status[i];
            }
            preid=nowid;
        }
        int ans=0;
        for(int i=0;i<=nowid;i++)
            ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
    return 0;
}