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 思路分析:题目要求找出最短的逃亡路径,但是与一般的问题不同,该问题增加了门与钥匙约束条件: 考虑一般的搜索问题的解答思路: 搜索算法即在解空间中搜索满足要求的答案,可以看做一棵不断生长的状态树,状 ...
一周排行
  • 


    		    nodejs fs.exists的處理
    官方API: http://nodejs.org/api/fs.html#fs_fs_ex
  • Magnifier.js
    Magnifier.js 是一个 JavaScript 库,能够幫助你在图像上实现放大镜效 ...
  • 参数:-Xmx20m -Xms20m -XX:NewRatio=1 -XX:SurvivorRatio=2 -XX:+PrintGCDetails -XX:PermSize=2m 结果: Heap PSYoungGe
  • 1.下载 zilib-1.2.7,提供压缩函数库 2.下载pcre-8.32,rewrite功能的依赖,需要安装 3.下载openssl-1.0.2a,可以访问https 4.下载nginx-1.6.2    1 .
  • 最近在开发Windows8 Metro App,使用JavaScript和HTML开发环境.所以操作数据綁定都是使用JSON格式数据.后台使用的是ASP.NET,因为项目相对较小,所有后台没有使用数据库,使用的XML
  • 题意:有n个小朋友,每个小朋友手上有一些糖,考虑每两个相邻的小朋友a.b,可以选择执行3种操作中的任一种:(1)a给b一粒糖(2)b给a一粒糖(3)不进行任何动作,问能否通过确定每两个相邻的小朋友的操作使得最终每个人
  • BZOJ1038ZJOI2008瞭望塔
    计算几何/半平面交 说是半平面交,实际上只是维护了个下凸壳而已……同1007水平可见直线
  • Author: Yuval Sinay MVP COMMUNITY SOLUTIONS CONTENT DISCLAIMER MICROSOFT CORPORATION AND/OR ITS RESPECTIVE S
  • 原版地址:http://code.angularjs.org/1.0.2/docs/guide/module   一.什么是Module? 很多应用都有一个用于初始化.加载(wires是这个意思吗?)和启动应用的ma ...
  •        REQUIRED:业务方法需要在一个容器里运行.如果方法运行时,已经处在一个事务中,那么加入到这个事务,否则自己新建一个新的事务.        NOT_SUPPORTED:声明方法不需要事务.如果方法