POJ 2288 Islands and Bridges（状压dp）-白红宇

POJ 2288 Islands and Bridges（状压dp）

阅读量：5125 次

发布时间：2019-06-13

本文共 1388 字，大约阅读时间需要 4 分钟。

题意：

有n个岛屿，每个岛屿有一个权值V，一条哈密顿路径C1，C2，...Cn的值为3部分之和：

第1部分，将路径中每个岛屿的权值累加起来；第2部分，对路径中的每条边（Ci，Ci+1），将成绩Vi×Vi+1累加起来；第3部分，当路径中连续的3个岛屿Ci、Ci+1和Ci+2形成一个三角形，即在岛屿Ci和Ci+2之间有一座桥，则把乘积Vi×Vi+1×Vi+2累加起来。

寻找权值最大的哈密顿路径和其路径数。

思路：

用d【status】【i】【j】表示当前状态为status，并且最后两个顶点分别为 i 和 j 时的最大权值，同理，ways【status】【i】【j】表示此时对应的路径的数量。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               10 #include
               11 #include
               
                 12 using namespace std; 13 typedef long long ll; 14 typedef pair
                
                  pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 1000 + 5; 17 18 int n, m; 19 20 int val[13]; 21 int g[13][13]; 22 ll d[1<<13][13][13]; 23 ll ways[1<<13][13][13]; 24 25 int main() 26 { 27 //freopen("in.txt","r",stdin); 28 int T; 29 scanf("%d",&T); 30 while(T--) 31 { 32 memset(g,0,sizeof(g)); 33 memset(d,-1,sizeof(d)); 34 memset(ways,0,sizeof(ways)); 35 36 scanf("%d%d",&n,&m); 37 for(int i=0;i
                 
                  -1) 63 { 64 for(int k=0;k
                  
                   maxvalue) 97 { 98 maxvalue=d[s][i][j]; 99 maxways=ways[s][i][j];100 }101 else if(d[s][i][j]==maxvalue)102 maxways+=ways[s][i][j];103 }104 }105 if(n!=1) maxways/=2; //因为正向和逆向是一样的，所以这里除2106 if(maxvalue==-1) puts("0 0");107 else printf("%lld %lld\n",maxvalue,maxways);108 }109 return 0;110 }

转载于:https://www.cnblogs.com/zyb993963526/p/7198529.html

你可能感兴趣的文章