首页 > 其他分享 >Projects

Projects

时间:2024-07-28 15:53:05浏览次数:14  
标签:无后效 cnt 200005 int ll long Projects

原题链接

题解

在日期上设计 无后效性 但是 \(1e9\)
发现真空点去掉对答案也没有影响,故对所有线段的端点离散化处理,然后再做无后效性处理

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll x[200005],y[200005],v[200005];

struct node
{
    int id,v;
};

ll dp[400005]={0};

void solve()
{
    ll n;
    cin>>n;

    map<ll,ll> q;
    for(ll i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>v[i];

        q[x[i]];
        q[y[i]];
    }

    int cnt=0;

    for(auto &it:q) it.second=++cnt;


    vector<node> G[cnt+1];
    for(int i=1;i<=n;i++)
    {
        G[q[y[i]]].push_back({q[x[i]]-1,v[i]});
    }

    for(int i=1;i<=cnt;i++)
    {
        dp[i]=dp[i-1];//这一天什么也没做

        for(auto from:G[i])
        {
            dp[i]=max(dp[from.id]+from.v,dp[i]);//刚刚完成一项任务
        }
    }

    cout<<dp[cnt]<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}



标签:无后效,cnt,200005,int,ll,long,Projects
From: https://www.cnblogs.com/pure4knowledge/p/18328302

相关文章