HDU3362+状态压缩

dp[ i ]表示该状态下得所需花费。

HDU3362+状态压缩
HDU3362+状态压缩
 1 /*
 2 状态压缩dp
 3 dp[i] = min( dp[ i-j ]+cost[ j ] );
 4 由i-j的状态转到i的状态
 5 */
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<stdlib.h>
 9 #include<iostream>
10 #include<math.h>
11 using namespace std;
12 const int maxn = 20;
13 const double inf = 99.0;
14 const int maxm = (1<<20);
15 const double eps = 1e-8;
16 struct node{
17     double x,y;
18 }dot[ maxn ];
19 double dp[ maxm ];
20 double dis[ maxn ][ maxn ];
21 double dist( int i,int j ){
22     return sqrt( ( dot[i].x-dot[j].x )*( dot[i].x-dot[j].x )+( dot[i].y-dot[j].y )*( dot[i].y-dot[j].y ) );
23 }
24 int main(){
25     int n;
26     while( scanf("%d",&n),n ){
27         int sum,cnt,flag;
28         cnt = 0;
29         sum = 0;
30         for( int i=0;i<n;i++ ){
31             scanf("%lf%lf%d",&dot[i].x,&dot[i].y,&flag);
32             if( flag==1 ){
33                 sum += (1<<i);
34                 cnt++;
35             }
36         }
37         if(( n>1&&cnt<2 )( n==1&&cnt==0 )){
38             printf("No Solution\n");
39             continue;
40         }
41         for( int i=0;i<n;i++ )
42             for( int j=0;j<n;j++ )
43                 dis[ i ][ j ] = dist( i,j );
44         int N = (1<<n);
45         for( int i=0;i<N;i++ )
46             dp[ i ] = inf;
47         dp[ sum ] = 0.0;
48         for( int i=sum;i<N;i++ ){
49             if( dp[i]>inf ) continue;
50             for( int j=0;j<n;j++ ){
51                 if( i&(1<<j) )//j是固定的
52                     continue;
53                 double min1 = inf;
54                 double min2 = inf;
55                 for( int k=0;k<n;k++ ){//找出min1,min2
56                     if( i&(1<<k) ){
57                         if( min1>dis[ j ][ k ] ){
58                             min2 = min1;
59                             min1 = dis[ j ][ k ];
60                         }
61                         else if( min2>dis[ j ][ k ] ){
62                             min2 = dis[ j ][ k ];
63                         }
64                     }
65                 }
66                 dp[ i(1<<j) ] = min( dp[ i(1<<j) ],dp[i]+min1+min2 );
67             }
68         }
69         printf("%.6lf\n",dp[ N-1 ]);
70     }
71     return 0;
72 }
View Code

 

更多相关文章
  • Corn Fields Time Limit: 2MS   Memory Limit: 65536K Total Submissions: 5763   Accepted: 3052 Description Farmer John has purchased a lush new rectangul ...
  • 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1885 题目意思: 给一个矩阵,给一个起点多个终点,有些点有墙不能通过,有些点的位置有门,需要拿到相应颜色的钥匙才能打开,问到达终点的最短步数. 解题思路: BFS+状态压缩. 将每种颜色对应一个二进制 ...
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3681 前些天花时间看到的题目,但写出不来,弱弱的放弃了.没想到现在学弟居然写出这种代码来,大吃一惊附加敬仰之情.这里借用下他的成果,好好学习吧,骚年*** Sample Input 5 5 GDDSS ...
  • HDU 2809 God of War(DP + 状态压缩)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2809 题目大意:给出战神吕布的初始攻击力ATI.防御力DEF.生命值HP.每升一级增加的攻击力In_ATI,增加的防御力In_DEF和增加的生命值In_HP.然后给出n个敌人的攻击力.防御力.生命值和杀 ...
  • HihoCoder第九周 状态压缩 二 与POJ2411总结
    在此我向各位博友求助,特别想知道除了HihoCoder上面的结果要对1e9+7取余之外,这两道题还有什么其他的问题,都是骨牌覆盖问题,都是状态压缩+dp,为什么我能过poj2411的程序过不了HihoCoder,还不是其他诸如TimeLimited,而是Wrong Answer,这个问题我想了很久, ...
  • 题目大意     N头牛,M个谷仓,每个牛c都有它喜欢的若干个谷仓,现在要将这N头牛安排进谷仓,使得每个牛都位于它喜欢的谷仓,而每个谷仓只能有一头牛.求安排的方案总数.N, M <= 20 题目分析     将M个谷仓视为一个整数的M个位,位i为1表示谷仓i被牛占用,否则表示谷仓i没有被牛占用 ...
  • poj1699(状态压缩dp)
    可能没有完全读懂题意. 个人觉得 acca aa  答案应该是4. 然后就是dp了..这题数据量小很多方法都可以,数据也水暴力据说都能过.. 还有就是我竟然没有用扩展kmp优化下... 太无耻了,我是因为找扩展kmp的题才来看这题的.     Best Sequence Time Limit: 1M ...
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1429 思路分析:题目要求找出最短的逃亡路径,但是与一般的问题不同,该问题增加了门与钥匙约束条件: 考虑一般的搜索问题的解答思路: 搜索算法即在解空间中搜索满足要求的答案,可以看做一棵不断生长的状态树,状 ...
一周排行
  • Android系统中Bitmap是否有调用recycle方法的必要性? Bitmap调用recycle? When Bitmap有一个recycle方法,意思很简单,回收Bitmap的空间. Q 1: Bitmap是 ...
  • 記一次Url重寫_發布之後iis 404
        把api封装完,客户要求app的url能不能不变(客户之前用的php的api开发a
  • 随着网络安全(例如:登录安全等)要求的不断提升,越来越多的登录应用在登录时添加了验证码登录,而验证码生成算法也在不断的进化,因而对含登录态的自动化测试脚本运行造成了一定程度的困扰,目前解决此种问题的方法主要有如下三种 ...
  • 很久之前装了QTP,官网下载的试用版,今天打开就发现不能用了.悲剧T T..肿么辦呢,百度一下,你就知道!好了,言归正传,网上主要有两种方法,一种是直接安装破解版,一种是安装好了再破解,那我肯定选第二种,因为前面都说
  • 到新公司一个周了,这家公司算是一家小型公司吧,业务基本都是教育方向的,比较蛋疼也是比较好的一点是这家公司没有自己的开发框架. 我应聘的是Java的后端开发,好吧,自学如何搭框架(开发2年半,苦逼的自己都不会搭基本的框
  • ShortcutMapper – 熱門應用程序的可視化快捷鍵
    ShortcutMapper 是一个流行应用程序的键盘快捷键映射.该应用程序使用 Ajax
  •   既然有set方法赋值,为什么还需要构造方法赋值呢?    当对象初始化时,必须用到某些属性,没有某些属性无法完成对象的创建时.构造方法赋值的作用就体现出来了.    set方法要更加灵活,因为对象在创建的过程构造
  • 今天用yum安装软件时报错: [[email protected] yum.repos.d]# yum -y install ipvsadm Loaded plugins: rhnplugin, security This syst
  • 问题描述: 管理员ID文件被设置为允许超期,同时又没有其他ID文件可以用于访问服务器.如果尝试用已经超期的管理员ID访问服务器,将会遇到如下错误: "服务器错误 - 你的证书已经过期" 此时没有其 ...
  • 本文转自:http://blogs.msdn.com/b/jorgepc/archive/2008/02/12/ssis-error-dts-e-cannotacquireconnectionfromconnecti