洛谷P2439 [SDOI2005]阶梯教室设备利用(带权区间…

2018-07-06 01:20:14来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定,如果两个演讲时间有部分或全部重复,那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室,也就是说,我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

题目描述

请写一个程序:

读入所有演讲的起始和终止时间;

计算最大的可能演讲总时间;

输入输出格式

输入格式:

 

第一行包括一个正整数n,n<=10000,为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k,0<=p< k<=30000。这样的一对整数表示一个演讲由时间p开始到时间k结束。

 

输出格式:

 

输出唯一的一个整数,为最长的演讲总时间。

 

输入输出样例

输入样例#1: 复制
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
输出样例#1: 复制
16

 

裸的带权区间覆盖问题,所有的区间权值都为$r - l$

设$f[i]$表示时间为$i$时的最大代价,转移的时候吧所有区间都存下来

枚举右端点为$i$的区间

 

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
vector<int> v[MAXN];
int f[MAXN], mx;
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        int x = read(), y = read();
        v[y].push_back(x);
        mx = max(mx, y);
    }
    for(int i = 0; i <= mx; i++) {
        f[i] = f[i - 1];
        for(int j = 0; j < v[i].size(); j++) 
            f[i] = max(f[i], f[v[i][j]] + i - v[i][j] );
    }
    printf("%d", f[mx]);
    return 0;
}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:MySQL与DevC++的连接问题

下一篇:洛谷P2052 [NOI2011]道路修建(树形DP)