当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 洛谷P2439 [SDOI2005]阶梯教室设备利用(带权区间覆盖)

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

2018年07月04日  | 移动技术网IT编程  | 我要评论

皇陵有宝不予贼子,哑巴小新娘总裁的逃妻,金诗麦

题目背景

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

题目描述

请写一个程序：

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

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

输入输出格式

输入格式：

 

第一行包括一个正整数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;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网