lanqiao oj 17136 星球(状态压缩dp)

简介: lanqiao oj 17136 星球(状态压缩dp)

用户登录

这个题和坐标搜寻差不多

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std ;
const int N = 20 , M = 110 ;;
double f[1<<N][20] ;
int x[M] ,y[M] , z[M] ,w[M] ;
double get_dis(int a ,int b ){//求直线距离 
  return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a] - y[b]) * (y[a] -y[b]) + (z[a] - z[b]) * (z[a]-z[b])) ;
}
int main(){
  int n ;
  cin >> n ;
  for(int i = 0  ;i < n ; i++){
    cin >> x[i] >> y[i] >> z[i] >>w[i];
  }
  memset(f,127,sizeof(f));
  f[0][0] = 0 ;
  for(int i = 0 ; i < n ; i ++) f[1<<i][i] = 0 ;
  for(int i = 0 ; i < 1 << n  ; i++){
    for(int j = 0 ; j < n ; j ++){
      for(int k = 0 ; k < n ; k ++){
        if((i>>j&1) && (i ^(1<<j)) >> k & 1) {//1. j存在于i中 2. k 于 j 不相等 ,并且k存在于i中 
          f[i][j] = min(f[i][j] , f[i ^(1<<j)][k] + get_dis(k,j) * w[j]);
        }
      }
    }
  }
  double ans = f[(1<<n)-1][0] ;
  for(int i = 1 ; i < n ; i ++) ans = min(ans , f[(1<<n)-1][i]) ;
  printf("%.2lf" , ans) ; 
}
目录
相关文章
|
2月前
lanqiao OJ 1505 剪邮票
lanqiao OJ 1505 剪邮票
27 0
|
2月前
lanqiao OJ 364 跳石头
lanqiao OJ 364 跳石头
34 6
|
2月前
lanqiao OJ 182 小朋友崇拜圈
lanqiao OJ 182 小朋友崇拜圈
29 2
|
2月前
lanqiao oj 1135 蓝桥幼儿园(并查集)
lanqiao oj 1135 蓝桥幼儿园(并查集)
27 0
|
2月前
lanqiao oj 1121 蓝桥公园(floyd)
lanqiao oj 1121 蓝桥公园(floyd)
43 0
|
2月前
lanqiao oj 186 糖果(状态压缩dp)
lanqiao oj 186 糖果(状态压缩dp)
15 0
|
2月前
|
BI
lanqiao OJ 蜗牛
lanqiao OJ 蜗牛
19 0
|
2月前
lanqiao OJ 2097 青蛙过河
lanqiao OJ 2097 青蛙过河
11 0
|
2月前
lanqiao OJ 234 大胖子走迷宫
lanqiao OJ 234 大胖子走迷宫
11 0
|
2月前
lanqiao OJ 102 青蛙跳杯子
lanqiao OJ 102 青蛙跳杯子
26 0