时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：
100%数据满足n < = 9。所有输入的数绝对值不超过1000。
输入描述:
第一行一个整数n，表示碗的数目。 以下n行，每行三个整数h，r1，r2。分别表示碗高及两个半径。其中r1<r2
输出描述:
仅一个数，表示最小的高度。答案四舍五入取整。
示例1
输入
复制
3
50 30 80
35 25 70
40 10 90
输出
复制
55
题解：
n<9，所以直接枚举就行，挨个试一遍取最优解
碗的叠放分几种情况：
当前的总高度应该是上底相对于上个碗的高度+上个碗底的高度
一个一个的放，然后看看哪一种情况下高度最高，暴力就完事了
思路很简单，但实现有点麻烦
斜率：2*h/（x1-x2）
代码：
我调了一阵子都没a。。。放弃了
直接借用大佬代码，参考处理的细节
代码选自
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
double h[maxn], r1[maxn], r2[maxn], tmp[maxn];
double calc(int x, int y) {
if (r1[x] > r2[y])//第一种情况
return h[y];
if (r2[x] < r1[y])//
return 0;
if ((r2[x] - r1[x]) * h[y] <= (r2[y] - r1[y]) * h[x]) {
if (r1[x] <= r1[y]) return 0;
return h[y] * (r1[x] - r1[y]) / (r2[y] - r1[y]);
}
if (r2[x] > r2[y])
return max(0.0, h[y] - h[x] * (r2[y] - r1[x]) / (r2[x] - r1[x]));
return max(0.0, h[y] * (r2[x] - r1[y]) / (r2[y] - r1[y]) - h[x]);
}
int id[maxn];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> h[i] >> r1[i] >> r2[i], id[i] = i;
double ans = inf, res = 0;
do{
res = 0;
for (int i = 1; i <= n; i++){
tmp[i] = 0;
for (int j = 1; j < i; j++)
tmp[i] = max(tmp[i], tmp[j] + calc(id[i], id[j]));
res = max(tmp[i] + h[id[i]], res);
}
ans = min(ans, res);
}while(next_permutation(id + 1, id + 1 + n));
printf("%d\n",(int)(ans+0.5));
return 0;
}
京公网安备 11010502036488号