hdu 1565 체크 수 (1) (DP 상태 압축)

체크 개수 (1)
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2585    Accepted Submission(s): 976
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
 
사고방식: 상태 압축 DP, 이전 상태 에서 다음 상태 로 기록.모든 상 태 를 매 거 하여 일치 하 는 합 법 적 인 상 태 를 찾 습 니 다.
        나 를 놀 라 게 한 것 은 이 코드 가 468 MS 만 달 렸 다 는 것 이다. 그 럴 리 가 있 겠 는가?나 혼자 20 팀 나 왔 어.AC 라 니,
      항 저 우의 이 문제 의 데이터 가 얼마나 약 한 지 정말 모르겠다.
   다 들 이 팀 의 데 이 터 를 뛰 어 다 니 면서 얼마나 걸 리 는 지 보 세 요.
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 
 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[2][28659];
int low[28659],pos;
int n;
int map[33];
void ini()
{ pos=0;
  for(int i=0;i<1<<n;i++)
    if(!(i&(i<<1)))
    low[pos++]=i;
}
int get(int x)
{
  int ret=0,t=0;
  while(x)
  {
    if(x&1)ret+=map[t];
    t++;x>>=1;
  }
  return ret;
}
int main()
{ ///cout<<(1<<22)<<endl;
  while(cin>>n)
  { memset(dp,0,sizeof(dp));
    int v=0,_max=0;
    ini();
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
        cin>>map[j];
      /*if(!i)
      { for(int j=0;j<pos;j++)
        dp[v][low[j]]=get(low[j]);
      }
       else
       {*/
         for(int j=0;j<pos;j++)
         { int ma=0;
           for(int k=0;k<pos;k++)
           {
             if(low[j]&low[k])continue;
             if(ma<dp[v^1][k])
              ma=dp[v^1][k];
           }
           dp[v][j]=ma+get(low[j]);
           _max=max(_max,dp[v][j]);
         }v^=1;
      // }

    }

    cout<<_max<<"
";
  }
}