UVa 1354 枚举子集 Mobile Computing
2024-09-06 18:36:49
只要枚举左右两个子天平砝码的集合,我们就能算出左右两个悬挂点到根悬挂点的距离。
但是题中要求找尽量宽的天平但是不能超过房间的宽度,想不到要怎样记录结果。
参考别人代码,用了一个结构体的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 ;
}
代码君
最新文章
- entityframework学习笔记--009-使用原生sql语句操作数据
- MS CRM 2013 Plugin 注册工具登录后空白
- 记录一些PHP7RCC1编译问题
- React入门--------JSX
- Saltstack-进阶篇
- OC - 21.CALayer核心要点及实例解析
- CSS布局方案之圣杯布局
- InputStream和OutputStream 何时使用
- .net 获取远程访问的ip
- 深度学习网络中numpy多维数组的说明
- c++中段自评
- spfa+01 规划
- css文本溢出隐藏显示省略号(单行+多行)
- Python3 tkinter基础 Canvas create_polygon 画三角形
- 【推荐】介绍两款Windows资源管理器,Q-Dir 与 FreeCommander XE(比TotalCommander更易用的免费资源管理器)
- BZOJ1342 [Baltic2007]Sound静音问题
- Eclipse解决运行、启动缓慢问题思路
- python之追溯函数调用及错误日志详细打印
- Django MiddleWare初识
- Django+Nginx+uwsgi搭建自己的博客(五)