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