poj2288(Islands and Bridges) 状压DP - c++编程基础

TOP

poj2288(Islands and Bridges) 状压DP

2015-07-24 05:50:47 来源: 作者: 【大中小】浏览:4次

题意：每个点有一个权值Vi，找一条哈密顿路径，路径的权值来自三条：1 路径上的Vi之和 2 所有相邻点对ij的Vi*Vj之和 3 相邻连续三点i,j,k(并且三点要构成三角形)Vi*Vj*Vk之和。

解法：dp[st][i][j]表示从j走到i并且剩下集合st没有走的最大权值。关于路径书，在转移的时候顺便计算即可；这道题令自己恶心了好久，最后原因是自己犯了一个严重错误，题目读错了，没有读到Vi*Vj*Vk要保证ijk能够构成一个三角形，在程序改一点判断ik是否有边即可。当然还要注意路径数可能超int，以及特判一个点的情况；

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               //freopen (in.txt , r , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=14; const int INF=1e9+7; int num[Max]; LL dp[1<
              
                vec[Max]; int n,m; LL getdp(int st,int i,int j) { if(dp[st][i][j]!=-1) return dp[st][i][j]; LL ans=-INF; LL sum=0; for(int l=0; l
               
                ans) { sum=cnt[st-(1<
                
                 >t; while(t--) { memset(rem,0,sizeof rem); scanf(%d%d,&n,&m); int sum=0; for(int i=0; i
                 
                  ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 11426 - GCD - Extreme (II) ..	下一篇：LeetCode-Insertion Sort List (P..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: