设为首页 加入收藏

TOP

hihocoder1170（状压dp）
2015-11-21 01:01:55 来源: 作者: 【大 中 小】 浏览:1次
Tags：hihocoder1170 状压
题意：

小冰的N个机器人兄弟排成一列，每个机器人有一个颜色。现在小冰想让同一颜色的机器人聚在一起，即任意两个同颜色的机器人之间没有其他颜色的的机器人。假设任意相邻的两个机器人可以交换位置，最少需要多少次交换？N<16，颜色种类不超过16种。

解法：一个明显的结论是：交换机器人时，相同颜色的机器人不会发生交换（保持他们之间的相对顺序）。即相当于给16种排序颜色。这总共有16！种结果，其dp方法雷同于旅行商问题的方法。

两个代码：

一种记忆化搜索，复杂度2^16*16*16：

?

/******************************************************
* @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=100010; const LL INF=0x3FFFFFFFFFFFFFFF; int a[Max]; LL num[20][20]; int sum[20]; LL ans[1<<17]; int n; int k; LL dfs(int state) { if(ans[state]!=-1) return ans[state]; ans[state]=INF; for(int i=0; i
              
               >t; int Case=1; while(t--) { memset(num,0,sizeof num); memset(sum,0,sizeof sum); memset(ans,-1,sizeof ans); scanf("%d%d",&n,&k); for(int i=0; i
               
                =0; i--) { for(int j=0; j
                
                  一种dp：
                 
?

                 
 复杂度2^16*16

                 
?

                 
/******************************************************
* @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=100010; const LL INF=0x3FFFFFFFFFFFFFFF; int a[Max]; LL num[20][20]; int sum[20]; LL ans[1<<17]; LL tool[1<<16][16]; int re[1<<16]; int n; int k; int main() { int t; cin>>t; int Case=1; for(int i=0; i<16; i++) re[1<
                              
                               =0; i--) { for(int j=0; j
                               
                                
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：LeetCode的medium题集合(C++实现).. 下一篇：Timus OJ 1057 数位dp

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: