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

题目背景

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

题目描述

请写一个程序：

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

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

输入输出格式

输入格式：

 

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