不知道算什么题。。。刚看的时候觉得是DP,因为前几天刚做的1069就跟这个很像,一个套一个的。所以想顺便撸一撸这两道题。
题意很简单,就是给你n个套娃,每个套娃的外体积和内容量,还有每个内体积的单价,当娃娃的内体积严格大于另一个的外体积时就可以把它套入,求最少的花费。
1069那道题也是一样的,相叠相叠。感觉是那道题还没有想透,所以这道题还是不大会做。
原先我想的是每次处理的时候可以找到一摞这样叠起来的套娃,(事实上确实可以。。)但是别人的程序每次只找一个最优的。。刚开始的时候是这样觉得的。。。。但是后来发现,两道题原理真心是一样的,感觉连代码都差不多,希望下次碰到的时候不要再做不出来了。
但是有个疑问,每次对一个盒子找到最优的之后,就不可能再后面的盒子中存在更优的情况吗(对于之前找打的那个盒子)。。。肯定是我的理论方面有点问题。。。算贪心方面的咩。。。
#include <stdio.h> #include <iostream> #include <algorithm> #include <cstring> using namespace std; #define inf 1e9 #define maxn 10000 #define ll __int64 struct node { ll out; ll in; ll c; }doll[maxn]; ll vis[maxn]; int cmp1(node a,node b) { return a.out>b.out; } int cmp2(int a,int b) { return doll[a].in>doll[b].in; } int main() { ll n; while(scanf("%I64d",&n)!=EOF) { ll i,j,k; ll sum=0; ll in[maxn]; for(i=0;i<n;i++) { scanf("%I64d%I64d%I64d",&doll[i].out,&doll[i].in,&doll[i].c); in[i]=i; } sort(doll,doll+n,cmp1); sort(in,in+n,cmp2); memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { ll tmp,max; tmp=max=-1; for(j=0;j<n;j++) { if(!vis[in[j]]&&doll[in[j]].in>doll[i].out&&doll[i].out*doll[in[j]].c>max) { max=doll[in[j]].c*doll[i].out; tmp=in[j]; // printf("doll[%I64d]=%I64d in[%I64d]=%I64d\n",i,doll[i].out,j,in[j]); } if(doll[i].in*doll[in[j]].c==max) { if(doll[in[j]].in>doll[tmp].in) tmp=in[j]; } } if(tmp!=-1) //以后if的判定要明确!!! { vis[tmp]=1; sum+=doll[tmp].in*doll[tmp].c-max; } } for(i=0;i<n;i++) if(!vis[i]) sum+=doll[i].in*doll[i].c; printf("%I64d\n",sum); } return 0; }