Codeforces777E. Hanoi Factory
3712 단어 Codeforces욕심
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
————————————————————————————————
제목은 n개의 접시의 내경 외경 높이를 제시하고, 외경이 작은 것은 확대할 수 없는 위쪽(동일할 수 있음)을 제시하며, 위의 외경은 반드시 아래의 내경보다 커야 하며, 최대 높이가 얼마나 되는지 묻는 것이다.
사고방식은 먼저 외경에 따라 큰 것부터 작은 것까지 순서를 정하고 같은 것은 내경에 따라 배열한다. 우리는 하나를 찾지 못하면 그 다음의 것도 가지 못하고 이럴 때 아래의 것만 갈 수 있다는 것을 분명히 알 수 있다.그래서 우리는 창고 유지 보수를 사용할 수 있다.
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
struct node
{
LL r,R,h;
} p[100005];
bool cmp(node a,node b)
{
if(a.R!=b.R)
return a.R>b.R;
return a.r>b.r;
}
stacks;
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1; i<=n; i++)
scanf("%lld%lld%lld",&p[i].r,&p[i].R,&p[i].h);
sort(p+1,p+n+1,cmp);
while(!s.empty())
s.pop();
LL ans=0;
LL mx=-1;
for(int i=1; i<=n; i++)
{
int flag=0;
while(!s.empty())
{
if(s.top().r>=p[i].R)
{
ans-=s.top().h;
s.pop();
}
else
{
ans+=p[i].h;
s.push(p[i]);
flag=1;
mx=max(mx,ans);
break;
}
}
if(flag==0)
{
ans+=p[i].h;
s.push(p[i]);
mx=max(mx,ans);
}
}
printf("%lld
",mx);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.