cf777E. Hanoi Factory

cf777E. Hanoi Factory

​​ Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.

There are n rings in factory’s stock. The i-th ring has inner radius ai, outer radius bi and height hi. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:

Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if bj ≤ bi. Rings should not fall one into the the other. That means one can place ring j on the ring i only if bj > ai. The total height of all rings used should be maximum possible. Input The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory’s stock.

The i-th of the next n lines contains three integers ai, bi and hi (1 ≤ ai, bi, hi ≤ 109, bi > ai) — inner radius, outer radius and the height of the i-th ring respectively.

Output Print one integer — the maximum height of the tower that can be obtained.

Examples Input 3 1 5 1 2 6 2 3 7 3 Output 6 Input 4 1 2 1 1 3 3 4 6 2 5 7 1 Output 4 Note In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.

In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

朴素o(n^2) 的dp 排序可以使杂乱无章的数据有序从而使得dp少一维

#include#include#define N 110000using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int a,b,h;}data[N];inline bool cmp(node a,node b){ return a.b==b.b?a.a>b.a:a.b>b.b;}long long f[N];int n;int main(){ //freopen("cf.in","r",stdin); n=read(); for (int i=1;i<=n;++i) data[i].a=read(),data[i].b=read(),data[i].h=read(); sort(data+1,data+n+1,cmp); for (int i=1;i<=n;++i){ for (int j=0;jdata[j].a) f[i]=max(f[i],f[j]+data[i].h); } } for (int i=1;i<=n-1;++i) f[n]=max(f[n],f[i]); printf("%I64d\n",f[n]); return 0;}

讲外半径按照从大到小顺序排列如果外半径相同则内半径按照从大到小排列

这样做的话我相当于递推一样的 从底下往上去做的

我做的时候查一下我下方比我外半径小1的内半径有哪些，然后他们垒起来的最大高度是多少

然后加上我自己的最大高度 这样就有可能构成我最终答案 然后把加上我的高度存储到我的内半径中，方便下一个的查找

#include#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16], *S, *T; if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}//离散化 struct node{ int a,b,h;}data[N];inline bool cmp(node a,node b){ return a.b==b.b?a.a>b.a:a.b>b.b;}long long s[N<<1];int n,size;vector list;inline void update(int x,long long tt){ while (x<=size*2){ s[x]=max(s[x],tt);x+=x&(-x); }}inline long long query(int x){ long long tmp=0; while (x){ tmp=max(tmp,s[x]);x-=x&(-x); } return tmp;}int main(){ freopen("cf.in","r",stdin); n=read(); for (int i=1;i<=n;++i) data[i].a=read(),data[i].b=read(),data[i].h=read(),list.push_back(data[i].a),list.push_back(data[i].b); sort(list.begin(),list.end()); for (int i=1;i<=n;++i){ data[i].a=lower_bound(list.begin(),list.end(),data[i].a)-list.begin()+1; data[i].b=lower_bound(list.begin(),list.end(),data[i].b)-list.begin()+1; } sort(data+1,data+n+1,cmp);long long ans=0;size=list.size(); for (int i=1;i<=n;++i){ long long ans1=query(data[i].b-1)+data[i].h; ans=max(ans,ans1); update(data[i].a,ans1); } printf("%I64d\n",ans); return 0;}

贪心方法：待填坑。。

填坑ing

首先按照外径从大到小，若外径相同按照内径从大到小排序

设立单调栈，维持内径与外径的关系，当栈内的内径大于等于我的外径时我需要把原有的元素弹出

直到栈内内径小于我的外径，我可以把新的入栈了，也就是可以叠上去了 然后每次叠都统计答案

谁知道最优解出现在哪里呢…

#include#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16], *S, *T; if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int a,b,h;}data[N];inline bool cmp(node a,node b){ return a.b==b.b?a.a>b.a:a.b>b.b;}int n;stack q;int main(){// freopen("cf.in","r",stdin); n=read(); for (int i=1;i<=n;++i) data[i].a=read(),data[i].b=read(),data[i].h=read(); sort(data+1,data+n+1,cmp);long long ans=0;long long max1=0; for (int i=1;i<=n;++i){ while (!q.empty()&&q.top().a>=data[i].b) ans-=q.top().h,q.pop(); if (!q.empty()) ans+=data[i].h,q.push(data[i]); else ans=data[i].h,q.push(data[i]); max1=max(max1,ans); } printf("%I64d\n",max1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。