J. Park life

題意

給你S個(gè)節(jié)點(diǎn),，E條邊,，每條邊有一個(gè)美麗值且每條邊能覆蓋[l,r)的點(diǎn)，詢問 \(k\in [1,n]\) 每個(gè)點(diǎn)最多被覆蓋k次的總美麗值的最大值

題解

把每個(gè)序列加上一個(gè)'源點(diǎn)'按照左端點(diǎn)小,，右端點(diǎn)大排序,，，則可以得到一個(gè)樹的先序序列,，從而可以構(gòu)建出一棵樹,。(不加源點(diǎn)會(huì)出現(xiàn)森林）

可以容易想到一個(gè)樹形dp，第i個(gè)節(jié)點(diǎn),，選擇i和不選擇i,\(dp[x][k]=max(\sum dp[son][k],dp[son][k-1] val[x]\))（但是會(huì)超時(shí)需要優(yōu)化）

因?yàn)閗一定是在k-1的基礎(chǔ)上額外選擇節(jié)點(diǎn),，所以答案一定是遞增的，可以用小根堆維護(hù)子樹的信息,。

設(shè)節(jié)點(diǎn)i的答案集合為\(dp[i]\),，代表 i 子樹中，所有頂點(diǎn)最多被''覆蓋''一次的答案集合：

對(duì)于葉子節(jié)點(diǎn)肯定只有val這一個(gè)權(quán)值（dp[i]=val）,，對(duì)于祖宗節(jié)點(diǎn),，答案集合為所有兒子集合的組合 val。因?yàn)橐蟠鸢高f增,，所以一定是從小到大或從大到小順序的組合,。

題意也可以這么理解，選過的邊不能重復(fù)選,，\(ans_k\)為不間斷選k次的最大值,，則上述的dp[0]從大到小分別是第i次每個(gè)點(diǎn)最多被覆蓋一次的答案，所以題目答案\(ans_k=\sum_{i\in son[0]} dp[i]\)

#include<bits/stdc  .h>
using namespace std;
const int N = 3e5 7;
int n,val[N];
 
struct node
{
    int l,r,pos;
 
}a[N];
 
vector <int> f[N];
priority_queue <long long >dp[N];
bool cmp(node x,node y)
{
    if(x.l==y.l)
        return x.r>y.r;
    return x.l<y.l;
}
 
struct compare
{
    bool operator ()(node x,node y)
    {
        if(x.l==y.l)
            return x.r>y.r;
        return x.l<y.l;
    }
};
 
void get_tree()
{
    stack <node>s;
    for(int i=n;i>=0;i--)
    {
        while(!s.empty()&&(a[i].r>=s.top().r))
        {
            f[a[i].pos].push_back(s.top().pos);
            s.pop();
        }
        s.push(a[i]);
    }
    
}
 
void dfs(int x)
{

    for(auto i:f[x])
    {
        dfs(i);
        if(dp[i].size()>dp[x].size())
        {
            swap(dp[x],dp[i]);//啟發(fā)式合并
        }
        vector <long long > temp;
        while(!dp[i].empty()) //答案集合的順序組合
        {
            temp.push_back(dp[i].top() dp[x].top());
            dp[i].pop();
            dp[x].pop();
        }
        for(auto j:temp)
        {
            dp[x].push(j);
        }
    }
    dp[x].push(val[x]);//加上val
}
void print()
{
    for(int i=0;i<=n;i  )
    {
        printf("i:%d\n",i);
        for(auto j:f[i])
        {
            printf("%d\n",j);
        }
        printf("\n");
    }
}
int main()
{
    scanf("%d",&n);
    a[0].l=0,a[0].r=1e6 5;
    for(int i=1;i<=n;i  )
    {
        scanf("%d %d %d",&a[i].l,&a[i].r,&val[i]);
        a[i].r--;
        a[i].pos=i;
    }
    sort(a,a n 1,cmp);
    get_tree();
 
    dfs(0);
    long long ans=0;
    for(int i=1;i<=n;i  )
    {
        if(!dp[0].empty())
        {
            ans =dp[0].top();//每次答案累加
            dp[0].pop();
        }
        printf("%lld ",ans);
    }
    return 0;
}
 

/*
6
1 2 10
2 3 10
1 3 21
3 4 10
4 5 10
3 5 19
 
4
1 5 1
2 5 1
3 5 1
4 5 1
 
*/