狂刷DP ---（四）

狂刷DP————（一）

-----poj 1185 炮兵阵地（位运算+DP）

最近在看位运算的提，此题是位运算+dp 也算氺题了，可是我却做了一中午啊！！！

 1 #include <stdio.h>
 2 #include <string.h> 
 3 #define max(a,b) (a) > (b) ? (a) : (b)  
 4  
 5 int stat[70],zhtai[110],dp[112][70][70],n,m,num[110],top;
 6 char map[110][20]; 
 7 //判断位置是否合适；  
 8 int ok(int x)
 9 {
10     if(x&(x<<1)){return 0;}
11     if(x&(x<<2)){return 0;}
12     return 1; 
13 }
14 //所有合法的状态
15 void hefa()
16 {
17     int i; 
18     top=0; 
19     int tole=1<<m;
20     for(i=0;i<tole;i++)
21     {
22         if(ok(i)){stat[++top]=i;} 
23     } 
24 }
25 //计算1的个数,也就是一行中炮最多数； 
26 int jisuan (int x)
27 {
28     int sum=0; 
29     while(x)
30     {
31         sum++;
32         x&=(x-1); 
33     } 
34     return sum; 
35 }
36 //判断与地形是否矛盾； 
37 int fit (int y,int x)
38 {
39     if(zhtai[x]&y)return 0;
40     return 1;    
41 } 
42 int main ()
43 {   char a; 
44     while(scanf("%d%d",&n,&m)!=EOF)
45     {    getchar(); 
46        for(int i=1;i<=n;i++)
47        {
48             for(int j=1;j<=m;j++)
49             {
50                scanf("%c",&a);
51                if(a=='H')
52                {
53                      zhtai[i]+=(1<<(j-1)); 
54                }    
55          } getchar(); 
56        } 
57         hefa(); 
58         memset(dp,-1,sizeof(dp));  
59        //初始化第一行； 
60        for(int i=1;i<=top;i++)
61        {
62              num[i]=jisuan(stat[i]); 
63              if(fit(stat[i],1))
64                dp[1][1][i]=num[i]; 
65        }
66        //dp....    
67        int i,j,h,k; 
68        for(i=2;i<=n;i++)
69        {
70              for(j=1;j<=top;j++)
71              { 
72              if(!fit(stat[j],i))continue; 
73                  for( k=1;k<=top;k++)
74                  {
75                      if(stat[j]&stat[k])continue; 
76                      for (h=1;h<=top;h++)
77                      {
78                          if(stat[j]&stat[h])continue; 
79                          if(dp[i-1][k][h]==-1)continue;  
80                              dp[i][h][j]= max(dp[i][h][j],dp[i-1][k][h]+num[j]); 
81                      } 
82                  }
83            } 
84        }
85       int max1=0;
86       for(int i=1;i<=n;++i) 
87       for(int j=1;j<=top;++j)
88         for(int k=1;k<=top;++k)
89         max1=max(max1,dp[i][j][k]); 
90       printf("%d
",max1); 
91     }
92 }

狂刷DP————（二）

--------poj 3254 Corn Fields

此题即上题后，比较容易，一次敲出，AC -----

 1 #include<stdio.h>
 2 #include<string.h> 
 3 #define max(a,b) (a) > (b) ? (a) : (b)  
 4 #define MOD 100000000  
 5 
 6 int stat[20],n,m,top,zhuang[1050],dp[20][1050]; 
 7 int ok(int x)
 8 {
 9     if(x&(x<<1))return 0;
10     return 1; 
11 }
12 int main ()
13 {   int a; 
14     while(scanf("%d%d",&n,&m)!=EOF)
15     {
16         for(int i=1;i<=n;i++)
17         {
18             stat[i]=0; 
19             for(int j=1;j<=m;j++)
20             {
21                 scanf("%d",&a);
22                 if(a==1){stat[i]+=(1<<(j-1));} 
23             } 
24         }
25         top=0; 
26         for(int i=0;i<=(1<<m);i++)
27             if(ok(i))
28               zhuang[top++]=i;
29          memset(dp,0,sizeof(dp)); 
30         for(int i=0;i<top;i++)
31         {
32             if((zhuang[i]&stat[1])==zhuang[i]) 
33                dp[1][zhuang[i]]=1; 
34              
35         } 
36         for(int i=2;i<=n;i++)
37         { 
38           for(int k=0;k<top;k++)
39           { 
40              if((zhuang[k]&stat[i])!=zhuang[k]){continue;} 
41                for(int j=0;j<top;j++)
42                 { 
43                    if(dp[i-1][zhuang[j]]&&(zhuang[k]&zhuang[j])==0) 
44                      {dp[i][zhuang[k]]=(dp[i][zhuang[k]]+dp[i-1][zhuang[j]]);} 
45                 } 
46            } 
47         }
48         int max1=0; 
49         for(int i=0;i<top;i++)
50         {
51             if(dp[n][zhuang[i]])
52               max1+=dp[n][zhuang[i]]; 
53         }
54         printf("%d
",max1%MOD); 
55     } 
56 }

狂刷DP————（三）

--------poj 3311 Hie with the Pie

此题两种解法（所掌握的），先贴出DP的；一样的水题。。。。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 20
 4 #define INF 20000
 5 
 6 int map[N][N],n,dp[1<<11][N];
 7 void floy ()
 8 {
 9     int k,i,j;
10     for(k=0;k<=n;k++)
11     for(i=0;i<=n;i++)
12     for(j=0;j<=n;j++)
13       if(map[i][j]>map[i][k]+map[k][j])
14          map[i][j]=map[i][k]+map[k][j];
15 }
16 int main ()
17 {
18     int a,i,j;
19     while(scanf("%d",&n)!=EOF&&n)
20     {
21       for(i=0;i<=n;i++)
22       {
23           for(j=0;j<=n;j++)
24           {
25               scanf("%d",&a);
26               map[i][j]=a;
27          }
28       }
29       floy();
30       int p;
31       memset(dp,-1,sizeof(dp));
32       dp[0][0]=0;
33       for(i=0;i<=((1<<n)-1);i++)
34       {
35           for(j=0;j<=n;j++)
36           {
37               if(dp[i][j]<0)continue;
38               for(int k=1;k<=n;k++)
39               {
40                   if(i&(1<<k-1))continue;
41                   p=i+(1<<k-1);
42                   if(dp[p][k]>dp[i][j]+map[j][k]||dp[p][k]<0)
43                      dp[p][k]=dp[i][j]+map[j][k];
44               }
45           }
46       }
47       for(p=-1,i=1;i<=n;i++)
48       {
49           if(p<0||dp[(1<<n)-1][i]+map[i][0]<p)
50              p=dp[(1<<n)-1][i]+map[i][0];
51       }
52       printf("%d
",p);
53     }
54 }

狂刷DP-------（四）

------HDU 3001 Travelling

这一题是poj 3311 的一个升级吧，做着还不错啊！!做了这两道提后对状态压缩位运算有了更加深的认识。。。这一类的提费了我很长一段时间啊，3天啊，，擦。。。。。发下牢骚。。》》》 - 。-

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 12
 4 #define INF 0x1f1f1f1f
 5 
 6 int Tree[N]={0,2,8,26,80,242,728,2186,6560,19682,59048};
 7 int map[N][N],dp[59059][N],f[59059][N],n;
 8 int min (int x,int y)
 9 {
10     return x<y?x:y;
11 }
12 void Z_fen (int n)
13 {
14     int j,now;
15     for(j=1;j<=Tree[n];j++)
16     {
17         now=j;
18         for(int k=1;k<=n;k++)
19         {
20            f[j][k]=now%3;
21            now/=3;
22            if(now==0)break;
23         }
24     }    
25 }
26 int main ()
27 { 
28     int m,i,j,k,news,a,b,len;
29     while(scanf("%d%d",&n,&m)!=EOF)
30     {
31         memset(map,INF,sizeof(map));
32         while(m--)
33         {
34             scanf("%d%d%d",&a,&b,&len);
35             if(len<map[a][b]){map[a][b]=map[b][a]=len;}
36         }
37         memset(f,0,sizeof(f));
38         Z_fen(n);
39         memset(dp,INF,sizeof(dp));
40         for(i=1;i<=n;i++){dp[Tree[i-1]+1][i]=0;}
41         int min1=INF;
42         /*for(i=1;i<=Tree[n];i++)
43         {
44         for(j=1;j<=n;j++)
45         {
46             printf("---%d+++",f[i][j]);
47         }
48         printf("
");
49         }*/
50         for(i=0;i<=Tree[n];i++)
51         {
52           int all=1;
53           for(j=1;j<=n;j++)
54           {
55             if(f[i][j]==0)all=0;
56             if(dp[i][j]==INF)continue;
57             for(k=1;k<=n;k++)
58             {   
59                 if(k==j)continue;
60                 if(f[i][k]==2||map[k][j]==INF)continue;
61                 news=i+(Tree[k-1]+1);
62                 dp[news][k]=min(dp[news][k],dp[i][j]+map[j][k]);
63             }
64           }
65           if(all)
66             for(j=1;j<=n;j++)
67             if(dp[i][j]<min1)
68             min1=dp[i][j];
69         }
70         if(min1==INF)printf("-1
");
71         else printf("%d
",min1);    
72     }
73 }