状态压缩DP

1：POJ 炮兵阵地

预先处理好情况，然后又类似格子取数的状压。

我们用DP[I][J][K]表示处理第I个格子，I-1格子的状态为J,I-2的格子为K,然后转移

1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<math.h>
5 #include<vector>
6 using namespace std;
7 char s[123][123];
8 int n,m,dp[123][123][123];
9 int ok[12345],mp[123][123];
10 vector<int>v[123];
11 int t;
12 int cal(int x)//计算能放的数量
13 {
14     int ans=0;
15     while (x){
16         if (x&1) ans++;
17         x/=2;
18     }
19     return ans;
20 }
21
22 void init()//预处理
23 {
24     t=0;
25     for (int i=0;i<(1<<m);i++)
26     {
27         if ((i<<1)&i) continue;
28         if ((i<<2)&i) continue;
29         ok[t++]=i;
30     }
31     for (int i=0;i<n;i++)
32     {
33         v[i].clear();
34         for (int j=0;j<t;j++)
35         {
36             int flag=1;
37             int top=0;
38             for (int k=0;k<m;k++)
39                 if (s[i][k]=='H'&&(ok[j]&(1<<k)))
40                 {
41                 flag=0;
42                 break;
43                 }
44             if (flag) v[i].push_back(ok[j]);
45       }
46     }
47 }
48
49 int main()
50 {
51     while (scanf("%d%d",&n,&m)!=EOF)
52     {
53         for (int i=0;i<n;i++) scanf("%s",s[i]);
54         init();
55         memset(dp,-1,sizeof(dp));
56         for (int i=0;i<v[0].size();i++) dp[0][i][0]=cal(v[0][i]);//处理1，2行的情况
57         for (int i=0;i<v[0].size();i++)
58             for (int j=0;j<v[1].size();j++)
59             if (!(v[0][i]&v[1][j])&&dp[0][i][0]!=-1)  dp[1][j][i]=dp[0][i][0]+cal(v[1][j]);
60
61         for (int i=2;i<n;i++)
62             for (int j=0;j<v[i].size();j++)
63               for (int k=0;k<v[i-1].size();k++){
64                 if (v[i][j]&v[i-1][k]) continue;
65                   for (int p=0;p<v[i-2].size();p++)
66                     if (dp[i-1][k][p]!=-1&&(v[i][j]&v[i-2][p])==0)
67                     dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+cal(v[i][j]));
68            }
69         int ans=0;
70         for (int i=0;i<t;i++)
71         for (int j=0;j<t;j++)
72         ans=max(ans,dp[n-1][i][j]);
73     printf("%d ",ans);
74     }
75   return 0;
76 }

2：POJ 3254

Corn Fields

入门提： 1 #include<stdio.h>

2 #include<string.h>
3 #include<math.h>
4 #include<vector>
5 #include<algorithm>
6 using namespace std;
7 int dp[22][1<<13];
8 int mp[20][20];
9 vector<int> v[2134];
10 const int M=100000000;
11 int n,m;
12 int t;
13 int state[123456];
14
15 void init()
16 {
17     t=0;
18     for (int i=0;i<n;i++)
19       for (int j=0;j<m;j++) scanf("%d",&mp[i][j]);
20     for (int i=0;i<(1<<m);i++)
21     {
22         if (i&(i>>1)) continue;
23         if (i&(i<<1)) continue;
24         state[++t]=i;
25         }
26     for (int i=0;i<n;i++)
27     {
28         v[i].clear();
29         for (int j=1;j<=t;j++){
30              int flag=1;
31         for (int p=0;p<m;p++)
32         if (mp[i][p]==0&&(state[j]&(1<<p)))
33         {
34             flag=0;
35             break;
36         }
37         if (flag) v[i].push_back(state[j]);
38       }
39     }
40 }
41
42 int main()
43 {
44     while (scanf("%d%d",&n,&m)!=EOF)
45     {
46          init();
47          memset(dp,0,sizeof(dp));
48          for (int i=0;i<v[0].size();i++) dp[0][i]=1;
49          for (int i=1;i<n;i++)
50          for (int j=0;j<v[i].size();j++){
51                 int now=v[i][j];
52                 for (int k=0;k<v[i-1].size();k++)
53                 if (!(now&(v[i-1][k])))
54                    {dp[i][j]+=dp[i-1][k];
55                              dp[i][j]%=M;
56                           }
57     }
58     int ans=0;
59     for (int i=0;i<v[n-1].size();i++){
60         ans+=dp[n-1][i];
61         ans%=M;
62     }
63     printf("%d ",ans);
64   }
65   return 0;
66 }　　　　　　　　

POJ:3311

哈密顿回路：N只有10，先求出任意一点的回路，难后状态压缩：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<list>
#define inf 123456789
int n;
int mp[12][12],dp[1<<12][12];
using namespace std;
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        if (n==0) break;
        for (int i=0;i<=n;i++)
            for (int j=0;j<=n;j++)
              scanf("%d",&mp[i][j]);
        for (int k=0;k<=n;k++)
            for (int i=0;i<=n;i++)
             for (int j=0;j<=n;j++)
              if (mp[i][j]>mp[i][k]+mp[k][j])
               mp[i][j]=mp[i][k]+mp[k][j];

        for (int i=0;i<(1<<n);i++)
            for (int j=1;j<=n;j++)
             if (i==(1<<(j-1))) dp[i][j]=mp[0][j];
          else if (i&(1<<(j-1)))
         {
            dp[i][j]=inf;
            for (int k=1;k<=n;k++)
            if (k!=j&&(i&(1<<(k-1))))
            dp[i][j]=min(dp[i][j],dp[(1<<(j-1))^i][k]+mp[k][j]);
          }
        int ans=inf;
        for (int i=1;i<=n;i++)
            ans=min(ans,dp[(1<<n)-1][i]+mp[i][0]);
      printf("%d
",ans);
    }
    return 0;
}
还有一种暴力方法，同时先预先求出点与点之间的最短路，然后求出全排列，再暴力枚举。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<list>
#define inf 123456789
int n;
int mp[12][12],dp[1<<12][12];
int a[12];
using namespace std;
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        if (n==0) break;
        for (int i=0;i<=n;i++)
            for (int j=0;j<=n;j++)
              scanf("%d",&mp[i][j]);
        for (int k=0;k<=n;k++)
            for (int i=0;i<=n;i++)
             for (int j=0;j<=n;j++)
              if (mp[i][j]>mp[i][k]+mp[k][j])
               mp[i][j]=mp[i][k]+mp[k][j];
          int ans=inf;
       for (int i=1;i<=n;i++) a[i]=i;
       do
       {
               int k=0;
               int t=0;
            for (int i=1;i<=n;i++)
            k+=mp[t][a[i]],t=a[i];
            k+=mp[t][0];
         ans=min(ans,k);
       }while (next_permutation(a+1,a+n+1));
      printf("%d
",ans);
    }
    return 0;
}

hdu 3001:

一辈子看错题：注意一个城市可以走两次

还有重边。

三进制表示很神奇

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 #include<list>
11 #define inf 0x3f3f3f3f
12 typedef long long ll;
13 using namespace std;
14 int state[12];
15 int vis[123456][12];
16 int dp[123456][13];
17 int mp[13][13];
18 int n,m;
19 void init()
20 {
21          state[0]=1;
22          for (int i=1;i<=10;i++)
23          state[i]=state[i-1]*3;
24      for (int i=0;i<=state[10];i++)
25      {
26         int tmp=i;
27         for (int j=0;j<=10;j++){
28             vis[i][j]=tmp%3;
29             tmp/=3;
30             }
31      }
32 }
33 
34 int main()
35 {
36       init();
37       while (scanf("%d%d",&n,&m)!=EOF)
38         {
39          memset(dp,inf,sizeof(dp));
40          memset(mp,inf,sizeof(mp));
41          for (int i=0;i<n;i++) dp[state[i]][i]=0;
42          while (m--)
43          {
44             int u,v,c;
45             scanf("%d%d%d",&u,&v,&c);
46             u--;
47             v--;
48             mp[u][v]=mp[v][u]=min(mp[u][v],c);
49          }
50             int ans=inf;
51             for (int i=0;i<state[n];i++){
52             int flag=1;
53             for (int j=0;j<n;j++){
54             if (vis[i][j]==0) flag=0;
55             if (dp[i][j]==inf) continue;
56             for (int k=0;k<n;k++)
57             if (k!=j) {
58             if (vis[i][k]>=2||mp[j][k]==inf) continue;
59             dp[i+state[k]][k]=min(dp[i+state[k]][k],dp[i][j]+mp[j][k]);
60             }
61           }
62          if (flag)
63              for (int j=0;j<n;j++) ans=min(ans,dp[i][j]);
64         }
65         if (ans==inf) ans=-1;
66         printf("%d
",ans);
67     }
68     return 0;
69 }

View Code

POJ2411;

　求N*M能放多少1*2的格子，虽然可以用二进制表示，但是转移方程状态又是另外一种写法

参考：http://blog.csdn.net/shiwei408/article/details/8821853

http://www.2cto.com/kf/201208/146894.html

这里解释了转移方程的写法。