Codeforces 777E 贪心或LIS+线段树

时间:2022-02-25 20:56:55

题目链接:Codeforces 777E

题目大意:有n个戒指,(n<=1e5),戒指有内径r,外径R,高度h,把它们堆成一个塔,要求是上面的戒指外径必须大于等于下面的,且上面的外径必须大于它下面一个的内径(不然就放不上去,会从中间掉下去),问塔最高能多高;

看到题目,想到了LIS,n个物体有序摆放,摆放有一定限制,求最大长度或价值,很明显是LIS。(前面刚做过一题LIS,所以这次才能很快想到。上次写的LIS:点这里
先按外径从大到小排序,外径相同,按内径从大到小排序。
定义dp[i]:=以第i个戒指为最顶层,所能达到的最大高度是多少
那么:dp[i]要么是只有一个i戒指,要么就是前面某个戒指再加一个i戒指(但要保证前面的戒指外径<=第i个的外径,第i个外径>前面的内径)
dp[i] = max(dp[i], dp[j]+h[i]);(j<i && j和i满足题目条件)
但是这样复杂度最差O(m^2)也就是1e10,会超时
无优化LIS超时代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>


using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 100;
ll n;
struct P
{
int r, R, h;
};
P p[MAXN];
inline bool cmp(const P &a, const P &b)
{
if(a.R == b.R) return a.r > b.r;
return a.R > b.R;
}
ll dp[MAXN];//dp[i]:=以i结尾最高

int main()
{
cin >> n;
for(int i=1; i<=n; ++i) scanf("%d%d%d", &p[i].r, &p[i].R, &p[i].h);
sort(p+1, p+n+1, cmp);
ll ans = 0;
for(int i=1; i<=n; ++i)
{
dp[i] = p[i].h;
for(int j=i-1; j>=1; --j)
{
if(p[j].r < p[i].R && p[i].R<=p[j].R) dp[i] = max(dp[i], dp[j] + p[i].h);
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}

题解说要用离散化线段树优化成O(m*longm),然而好复杂弱鸡不会。

在网上看到另一种解法,也是先排序,求出以每个戒指为最顶层,能达到的最大高度是多少,然后找出最大值。
但是用的方法比较机智,找以i为顶层的最大值时,并不是遍历[1,i-1]找最大值,而是用栈记录下以i-1为顶层时得到最大高度的方案,以i-1的方案为基础,如果第i个戒指不能放上去,那就删去最上面的那个,如果还不能放,再删去,直到能够把第i个戒指放上去。然后的得到的值就是以i为顶层的最大值。

简单的说,就是,以i为顶层能的到最大高度的堆放方案,是以i-1为顶层的最大高度方案,删去最上面会导致不能放i的那些戒指,再把i放上去。

为什么这样可以呢?因为如果要把i-1放上去,i-1下面的戒指内径必须小于i-1的外径,外径必须满足>=i-1的外径。
排序后第i个外径一定>=第i-1个,如果第i-1个无法放上去的,可能是最顶层那个的外径小于第i-1个的,那么其外径也肯定小于第i个的,第i个也不能放上去;
还可能是最顶层外径等于第i-1个的外径,但是最顶层的内径大于等于第i-1个的,同理,其内径也肯定大于第i个的外径,第i个也不能放上去;
(简单的说就是要放上戒指i所需要的条件比放上i-1更苛刻)
所以,综上,第i个为顶层的方案肯定是以第i-1为顶层的方案,删去上面不满足条件的戒指后得到的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>


using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 100;
ll n;
struct P
{
int r, R, h;
};
P p[MAXN];
inline bool cmp(const P &a, const P &b)
{
if(a.R == b.R) return a.r > b.r;
return a.R > b.R;
}

stack<P> sp;

int main()
{
cin >> n;
for(int i=1; i<=n; ++i) scanf("%d%d%d", &p[i].r, &p[i].R, &p[i].h);
sort(p+1, p+n+1, cmp);
ll ans = p[1].h;
ll sum = p[1].h;
sp.push(p[1]);
for(int i=2; i<=n; ++i)
{
while(!sp.empty() && p[i].R <= sp.top().r)
{
sum-=sp.top().h;
sp.pop();
}
sum+=p[i].h;
sp.push(p[i]);
ans = max(ans, sum);
}
cout << ans << endl;

return 0;
}