题目链接:这里
题意:每个玩具有占用的空间和内部可容纳的空间。规定每个玩具只能直接嵌套一个玩具,可以间接嵌套,即A套B,B再套C,但是不能A同时套B和C。A能套B的条件是A的内部空间严格大于B的占用空间。第i个玩具有一个单位花费ci,乘以该玩具内部还剩于的空间即为花费。要问的是经过适当的嵌套之后,最小花费是多少。
解法:贪心 显然,每次嵌套会使花费减少。对于每个玩具,如果要将它套进别的玩具里面,在条件允许的情况下肯定是找单位花费大的套,这样花费减小才快。按找单位花费从大到小排序,注意当花费一样的时候,内部体积从大到小。从小到大也可以过,应该是数据不严格?

//UVA Live 6424
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
struct node{
    int out, in, val;
    node(){}
    node(int out, int in, int val) : out(out), in(in), val(val) {}
    bool operator < (const node &rhs) const{
        if(val == rhs.val) return in > rhs.in;
        return val > rhs.val;
    }
}a[1010];

bool used[maxn];

int main(){
    int n;
    while(scanf("%d", &n) != EOF)
    {
        memset(used, 0, sizeof(used));
        for(int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].out, &a[i].in, &a[i].val);
        sort(a + 1, a + n + 1);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int nowv = 0;
            for(int j = 1; j <= n; j++){
                if(i != j && a[j].out < a[i].in && !used[j]){
                    nowv = max(nowv, a[j].out);
                }
            }
            if(nowv){
                for(int j = 1; j <= n; j++) if(!used[j] && a[j].out == nowv){
                    used[j] = 1;
                    break;
                }
            }
            ans = ans + (a[i].in - nowv) * a[i].val;
        }
        printf("%d\n", ans);
    }
    return 0;
}