新手光能
http://judge.codingtang.com/problem/1532/
1532 教室安排2
题目描述 Description
酷町堂在成立之初只有一个小教室，而班次却有很多，因此必须协调好每个班的上课起始时间和终止时间。如果有一个班是在8点至9点上课，则这个时间段不能安排别的课程，假设某一时刻一个班级结束，另一个班级就可以立即上课。现在有一些排课计划的时间表，为了满足更多的学生，请你设计出一种方案使得这一教室上课时间达到最长。 例如：现在有5个班级的上课时间表如下： 1 2 2 6 1 3 4 5 3 9 为了使得教室上课时间达到最长，应该选择1 3和3 9这两个班级，总的上课时间为8小时。
输入描述 Input Description
输入为N+1行；
第一行输入一个整数N，N<=5000，表示共有的N个班级等待排课，
以下的N行中，每行包含两个整数a，b，1<=a<=b<=30000，表示该班级课程的起始时间和终止时间。
输出描述 Output Description
输出一个整数，表示该教室最长的使用时间。
样例输入 Sample Input
5
1 2
2 6
1 3
4 5
3 9
样例输出 Sample Output
8
@葛新 @管理员 @陆麟瑞 @樊澄宇 @贾文卓 帮帮本蒟蒻
新手光能
动态规划
用struct l,r:int数组a储存每段时间，按结束时间排序（从小到大）排序
定义f[j]表示结束时间j以前最长使用时间
f[j]=max(f[j],f[a[i].l]+a[i].r-a[i].l);( 1<=i<=n a[i].r<=j<=max_r ) max_r表示最晚结束时间
for (int i=1;i<=n;i++)
{
for (int j=a[i].r;j<=max_r;j++)
{
f[j]=max(f[j],f[a[i].l]+a[i].r-a[i].l);
}
}输出f[max_r]
边界全赋0
求采纳 求采纳 求采纳
新手光能
初级天翼
和1217 数组接龙很像
新手光能
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct data {
int l,r;
};
data a[30010];
int f[30010];
bool cmp(data x, data y) {
if (x.r>y.r) return true;
if (x.r<y.r) return false;
return x.l<y.l;
}
int main() {
int n,max_r;
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);
max_r=a[n].r;
for (int i=1; i<=n; i++) {
f[i]=0;
f[j]=max(f[j],f[a[i].l]+a[i].r-a[i].l);
}
for (int i=1; i<=n; i++) {
for (int j=a[i].r; j<=max_r; j++) {
f[j]=max(f[j],f[a[i].l]+a[i].r-a[i].l);
}
}
cout<<f[max_r];
return 0;
}
不对吗？ @樊澄宇
缔造者
1
缔造者之神
1
