NC20464 [ZJOI2006]BOWL 碗的叠放(全排列枚举)

题目链接

题意：



题解：

AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
//const int N = 1e3 + 10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    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));
    cout << (int)(ans + 0.5);
    return 0;
}