题意：俄罗斯有一种玩具叫做套娃，一个大的只能嵌套一个比它内体积小的套娃 ，给你每个套娃的内体积和外体积，每个套娃内体积单位空体积的消耗，问你怎么样安排才能使得花费最小。
解题思路：这里我们知道，是优先去花费最大的那个套娃并且填掉它。
解题代码：
1 // File Name: 12895.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月16日 星期六 23时41分13秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 struct node{ 28 int x, y , c,ok; 29 }a[1005]; 30 int cmp(node a, node b) 31 { 32 return a.c > b.c ; 33 } 34 int main(){ 35 int n ; 36 while(scanf("%d",&n)!= EOF) 37 { 38 memset(a,0,sizeof(a)); 39 for(int i = 1;i <= n;i ++) 40 { 41 scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c) ; 42 a[i].ok = 1; 43 } 44 sort(a+1,a+1+n,cmp); 45 LL ans = 0 ; 46 for(int i = 1;i <= n;i ++) 47 { 48 int site = 0 ; 49 int mx = 0; 50 for(int j = 1;j <= n;j ++) 51 { 52 if(a[j].ok && a[i].y > a[j].x ) 53 { 54 if(a[j].x > mx) 55 { 56 mx = a[j].x; 57 site = j ; 58 } 59 } 60 } 61 if(site) 62 { 63 a[site].ok = 0 ; 64 } 65 ans += (a[i].y - mx)*a[i].c ; 66 } 67 printf("%I64d ",ans); 68 } 69 return 0; 70 }