Codeforces 777E 贪心或LIS+线段树

题目大意：有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;
}

秒客网

Codeforces 777E 贪心或LIS+线段树

相关文章