상태 압축 dp (hdu 2167, poj 2411)

hdu2167 http://acm.hdu.edu.cn/showproblem.php?pid=2167
N * N 판 자 를 지정 합 니 다. 안에 N * N 개의 숫자 가 있 습 니 다. 숫자 를 선택 하여 최대 와 최대 로 합 니 다.
선택 한 두 개의 숫자 가 서로 인접 하지 않도록 요구 합 니 다. 인접 은 상하, 좌우 와 대각선 이 서로 인접 합 니 다.
N < = 15 로 인해 프로그램 으로 각 줄 의 유효 상태 < 1600 개, 이러한 상 태 를 기록 한 다음 에 각 줄 이 현재 줄 의 이전 줄 의 상 태 를 매 거 한다 면 극단 적 으로 1600 * 1600 * 15 의 복잡 도, TLE 가 있 습 니 다.
그래서 여기 오래 걸 려 서 어떻게 최적화 할 지 생각 이 안 나 요.그리고 다른 사람의 코드 를 보고 인접 표 로 어떤 상 태 를 저장 하 는 지 알 게 되 었 습 니 다.이렇게 하면 그렇게 많이 열거 할 필요 가 없다.그래서 지 나 갔 어 요.

 1 #include <stdio.h>

 2 #include <string.h>

 3 #include <iostream>

 4 #include <sstream>

 5 using namespace std;

 6 int matrix[15][15];

 7 int dp[1<<15][15],situation[1600],bit[15],head[1000000],e;

 8 struct node

 9 {

10     int v,next;

11 }g[1000000];;

12 int max(const int &a, const int &b)

13 {

14     return a < b ? b : a;

15 }

16 

17 void addEdge(int u, int v)

18 {

19     g[e].v = v;

20     g[e].next = head[u];

21     head[u] = e++;

22 }

23 int count(int i, int ss, int n)//     i    s      

24 {

25     int ret = 0;

26     int j = 0;

27     for(j=0; j<n; ++j)

28     {

29         if(bit[j] & ss)

30             ret += matrix[i][j];

31     }

32     return ret;

33 }

34 bool check(int s, int ss,int n)//  s ss    

35 {

36     

37     if(s&ss) return false;

38     if((s<<1)&ss) return false;

39     if((s>>1)&ss) return false;

40     return true;

41 }

42 int main()

43 {

44     int n,i,j,m,s,ss;

45     char str[100];

46     bit[i=0] = 1;

47     for(i=1; i<15; ++i)

48         bit[i] = bit[i-1]<<1;

49     m = 1<<15;

50     for(i=0,j=0; i<m; ++i)

51         if(!(i&(i<<1)))//       

52             situation[j++]= i;

53     while(gets(str))

54     {

55         memset(dp,0,sizeof(dp));

56         e = 0;

57         memset(head,-1,sizeof(head));

58         n = 0;

59         do

60         {

61             j = 0;

62             stringstream scin(str);

63             while(scin>>matrix[n][j]) j++;

64             n++;

65             gets(str);

66             if(str[0]=='\0') break;

67 

68         }while(true);

69         m = 1<<n;

70         for(i=0;situation[i]<m; ++i)//         ，        

71             for(j=0; situation[j]<m; ++j)

72                 if(check(situation[i],situation[j],n))

73                     addEdge(i,j);

74         for(i=0; situation[i]<m; ++i)

75             dp[situation[i]][0] = count(0,situation[i],n);

76         for(i=1; i<n; ++i)

77             for(s=0;situation[s]<m; ++s)

78             {

79                 for(j=head[s];j!=-1;j=g[j].next)

80                 {

81                     dp[situation[g[j].v]][i] = max(dp[situation[g[j].v]][i],dp[situation[s]][i-1]+count(i,situation[g[j].v],n));

82                 }

83             }

84         int ans = 0;

85         for(i=0; situation[i]<m; ++i)

86         {

87             ans = max(ans,dp[situation[i]][n-1]);

88         }

89         printf("%d
",ans);

90     }

91     return 0;

92 }

 poj2411 http://poj.org/problem?id=2411
N * M 의 사각형 을 정 하고 1 * 2 의 행렬 로 채 우 고 채 우 는 방법 이 몇 가지 가 있 는 지 물 어보 세 요.N,M<=11
상태 압축 dp, 시간 복잡 도 는 N * (1 < < M) * (1 < M) 입 니 다. 인접 표 로 저장 할 수 있 습 니 다. 어떤 상태 가 서로 어 울 리 는 지, 이렇게 하면 모든 상 태 를 매 거 할 필요 가 없습니다.
상 태 는 어떻게 전 이 됩 니까?
우선 첫 번 째 줄 의 상 태 는 1 이 있 으 면 연속 적 인 두 개가 있어 야 한다. 즉, 단독 적 인 1 이 있어 서 는 안 된다.
두 번 째 줄 을 세로 로 놓 으 면 첫 줄 의 빈 자 리 를 채 우기 위해 서다.
현재 줄 의 상태 와 이전 줄 의 상태 가 충돌 하지 않 는 것 을 어떻게 판단 합 니까?자세 한 내용 은 bool check (int s, int ss) 함수 설명 참조

 1 #include <stdio.h>

 2 #include <string.h>

 3 #define LL __int64

 4 int n,m;

 5 int e,head[1000000];

 6 LL dp[1<<11][11];

 7 struct node

 8 {

 9     int v,next;

10 }g[1000000];

11 

12 void addEdge(int a, int b)

13 {

14     g[e].v = b;

15     g[e].next = head[a];

16     head[a] = e++;

17 }

18 void swap(int &a, int &b)

19 {

20     int t = a;

21     a = b;

22     b = t;

23 }

24 bool check(int s)

25 {

26     while(s)

27     {

28         if( (s&1) && ((s>>1)&1))

29             s>>=2;

30         else if( (s&1) && !((s>>1)&1))

31             return false;

32         else if(!(s&1))

33             s>>=1;

34         

35     }

36     return true;

37 }

38 bool check(int s, int ss)

39 {

40     for(int i=0; i<m; ++i)

41     {

42         if(!(s&1) && !(ss&1)) return false;//       0，             ,     

43         else if(!(s&1)&&(ss&1)) 

44         {

45             s>>=1;ss>>=1;continue;//    0，      

46         }

47         else if((s&1)&&!(ss&1)) 

48         {

49             s>>=1;ss>>=1;continue;//       1，       

50         }

51         else if((s&1)&&(ss&1))//                1，           

52         {

53             s>>=1,ss>>=1;i++;

54             if((s&1)&&(ss&1)) //      ，           1

55             {

56                 s>>=1;ss>>=1;continue;

57             }

58             else return false;

59         }

60     }

61     return true;

62 }

63 int main()

64 {    

65     int s,ss,t,i,j;

66     LL ans;

67     while(scanf("%d%d",&n,&m),n)

68     {

69         memset(dp,0,sizeof(dp));

70         if(n<m) swap(n,m);

71         ans = 0;

72         t = 1<<m;

73         memset(head,-1,sizeof(head));

74         e = 0;

75         for(s=0; s<t; ++s)

76             for(ss=0; ss<t; ++ss)

77                 if(check(s,ss))

78                     addEdge(s,ss);

79         if((n*m)%2==0)

80         {

81             for(s=0; s<t; ++s)

82                 if(check(s))

83                     dp[s][0] = 1;

84             for(i=1; i<n; ++i)

85                 for(s=0; s<t; ++s)

86                     for(j=head[s];j!=-1 && g[j].v<t;j=g[j].next)

87                         dp[g[j].v][i] += dp[s][i-1];

88                         

89             ans = dp[(1<<m)-1][n-1];

90         }

91         printf("%I64d
",ans);

92     }

93     return 0;

94 }