rockdu
题目背景
我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。
题目描述
请写一个程序：
读入所有演讲的起始和终止时间；
计算最大的可能演讲总时间；
输入输出格式
输入格式：
第一行包括一个正整数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： 复制 显然，如果选择了一个讲座，那么与其相交的讲座都不可以进行。这就是一个DAG模型。我们对时间轴建立一条单向的链，所有边权值为0。对每一个讲座的时间区间，我们由开始时间向结束时间连接一条边权为演讲时间长度的单向边。对DAG求最长路就行了。
16
显然，如果选择了一个讲座，那么与其相交的讲座都不可以进行。这就是一个DAG模型。我们对时间轴建立一条单向的链，所有边权值为0。对每一个讲座的时间区间，我们由开始时间向结束时间连接一条边权为演讲时间长度的单向边。对DAG求最长路就行了。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int dp[maxn], n, l, r, N = 30000;
vector<int > pos[maxn];
int main() {
scanf("%d", &n);
memset(dp, 0x3f, sizeof(dp)), dp[0] = 0;
for(register int i = 1; i <= n; ++i)
scanf("%d%d", &l, &r), pos[r].push_back(l);
for(register int i = 1; i <= N; ++i) {
dp[i] = dp[i - 1] + 1;
for(register int j = pos[i].size() - 1; j >= 0; --j)
dp[i] = min(dp[pos[i][j]], dp[i]);
}
printf("%d", N - dp[N]);
return 0;
}
没有帐号? 立即注册