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\n

",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\n

",ans);

64   }

65   

return 

0;

66 }　　　　　　　　

                                                                                                                                                         

POJ:3311

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

#include 
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define inf 123456789int 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<
                
               
              
             
            
           
          
         
        
       

#include 
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define inf 123456789int 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\n",ans); } return 0;}
                 
                
               
              
             
            
           
          
         
        

hdu 3001:

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

还有重边。

三进制表示很神奇

1 #include 
         
           2 #include
          
            3 #include
           
             4 #include
            
              5 #include
             
               6 #include
              
                7 #include
               
                 8 #include
                
                  9 #include
                 
                  10 #include
                  
                   11 #define inf 0x3f3f3f3f12 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
                   
                    =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
                   
                  
                 
                
               
              
             
            
           
          
         

 

　　

POJ2411;

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

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

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

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