【noip模拟赛7】上网

描述

假设有n个人要上网,却只有1台电脑可以上网。上网的时间是从1 szw 至 T szw ,szw是sxc,zsx,wl自创的时间单位,至于 szw怎么换算成s,min或h,没有人清楚。依次给出每个人在某个时间段内上网的快乐程度C(必须这个人在整个时间段内都在上网,才能获得快乐程度C,否则,快乐程度是0),请你得到使总的快乐程度达到最大的方案。

输入

第1行2个整数 n和T,含义如题目所述;

接下来有n个这样的结构(每两个相邻的结构之间有一空行,且第1个结构和第一行间有一空行):

第1行一个整数Mi,表示第i个人的时间段的个数;

接下来有Mi行,每行3个整数Xj,Yj,C,表示第i个人在[Xj,Yj]内上网的快乐程度为C,

因此有Xj-Yj-1=1,X1=1,Ymi=T,Xj<=Yj。

输出

仅输出一行,为总的最大的快乐程度。

输入样例 1 

3 10 

3
1 3 6
4 7 9
8 10 3

3
1 3 5
4 7 10
8 10 1

4
1 3 2
4 8 2
9 9 6
10 10 3

输出样例 1

25

提示

【样例说明】

在[1,3]内,安排1上网,快乐程度为6;

在[4,7]内,安排2上网,快乐程度为10;

在[8,8]内,不安排;

在[9,9]内,安排3上网,快乐程度为6;

在[10,10]内,安排3上网,快乐程度为3;

这是使总的快乐程度达到最大的方案,对应的值是25。

【数据范围】

对于30%的数据,n<=4,所有的Mi<=5,T<=20;

对于60%的数据,n<=100,所有的Mi<=100,T<=2000;

对于100%的数据,n<=500,所有的Mi<=500,T<=500000,所有的0<C<=10^9,并保证最终解Max<=10^9。

简单dp,vector[i]存结束时间为i的所有时间区间的开始时间和快乐程度,状态转移为:dp[i]=max(dp[i],dp[g[i][j].F-1]+g[i][j].S)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(5e5)+100
#define mod int(1e9)+7
using namespace std;
int dp[maxn];
vector<pii> g[maxn];
int main(){
    int n,T;sc2(n,T);
    FF(i,n){
        int x;sc(x);
        while(x--){
            int a,b,c;sc3(a,b,c);
            g[b].pb({a,c});
        }
    }
    mst(dp,0);
    for(int i=1;i<=T;++i){
        dp[i]=max(dp[i],dp[i-1]);
        for(int j=0;j<g[i].size();++j){
            dp[i]=max(dp[i],dp[g[i][j].F-1]+g[i][j].S);
        }
    }
    pr(dp[T]);
    return 0;
}

 

发表评论,支持MarkDown语法