只要枚举左右两个子天平砝码的集合,我们就能算出左右两个悬挂点到根悬挂点的距离。

但是题中要求找尽量宽的天平但是不能超过房间的宽度,想不到要怎样记录结果。

参考别人代码,用了一个结构体的vector,保存每个集合合法方案的左右两端最长的距离。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#define MP make_pair
#define Ft first
#define Sd second
using namespace std; typedef pair<double, double> PDD; const int maxn = ;
const int maxs = ; vector<PDD> tree[maxs]; int n;
double r;
double a[maxn], w[maxs];
bool vis[maxs]; int bitcount(int x)
{
int ans = ;
while(x) { ans += (x & ); x >>= ; }
return ans;
} void dfs(int S)
{
if(vis[S]) return ;
vis[S] = true;
if(bitcount(S) == ) { tree[S].push_back(MP(, )); return ; } PDD t = MP(, );
for(int s1 = (S-)&S; s1; s1 = (s1-)&S)
{
int s2 = S ^ s1;
dfs(s1); dfs(s2);
double x1 = w[s2] / w[S], x2 = w[s1] / w[S];
for(int i = ; i < tree[s1].size(); i++)
for(int j = ; j < tree[s2].size(); j++)
{
t.Ft = max(x1 + tree[s1][i].Ft, tree[s2][j].Ft - x2);
t.Sd = max(x2 + tree[s2][j].Sd, tree[s1][i].Sd - x1);
if(t.Ft + t.Sd < r) tree[S].push_back(t);
}
}
} int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%lf%d", &r, &n);
for(int i = ; i < n; i++) scanf("%lf", a + i);
int all = ( << n) - ; for(int i = ; i <= all; i++)
{
w[i] = ;
tree[i].clear();
for(int j = ; j < n; j++) if(i & ( << j))
w[i] += a[j];
} memset(vis, false, sizeof(vis));
dfs(all);
double ans = -;
for(int i = ; i < tree[all].size(); i++) ans = max(ans, tree[all][i].Ft + tree[all][i].Sd);
if(ans < ) puts("-1");
else printf("%.9f\n", ans);
} return ;
}

代码君

最新文章

  1. entityframework学习笔记--009-使用原生sql语句操作数据
  2. MS CRM 2013 Plugin 注册工具登录后空白
  3. 记录一些PHP7RCC1编译问题
  4. React入门--------JSX
  5. Saltstack-进阶篇
  6. OC - 21.CALayer核心要点及实例解析
  7. CSS布局方案之圣杯布局
  8. InputStream和OutputStream 何时使用
  9. .net 获取远程访问的ip
  10. 深度学习网络中numpy多维数组的说明
  11. c++中段自评
  12. spfa+01 规划
  13. css文本溢出隐藏显示省略号(单行+多行)
  14. Python3 tkinter基础 Canvas create_polygon 画三角形
  15. 【推荐】介绍两款Windows资源管理器,Q-Dir 与 FreeCommander XE(比TotalCommander更易用的免费资源管理器)
  16. BZOJ1342 [Baltic2007]Sound静音问题
  17. Eclipse解决运行、启动缓慢问题思路
  18. python之追溯函数调用及错误日志详细打印
  19. Django MiddleWare初识
  20. Django+Nginx+uwsgi搭建自己的博客(五)

热门文章

  1. Ionic开发-搭建开发环境
  2. Java Lambda表达式教程与示例
  3. css文字与文本相关样式
  4. Java基础语法(数组)
  5. HDU 4507 吉哥系列故事——恨7不成妻 (数位DP)
  6. 51nod 1101 换零钱
  7. .net代码获取节点以及读取属性
  8. Typescript的优势
  9. Vue中使用computed与watch结合实现数据变化监听
  10. 2018.5.11 Java利用反射实现对象克隆