新手光能
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
求采纳 求采纳 求采纳
新手光能
#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;
}
不对吗? @樊澄宇