问题标题: 1532 教室安排2 怎么写???求大佬帮助!!!

1
1
已解决
陶梓锐
陶梓锐
新手光能
新手光能

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

 

 

 

@葛新 @管理员 @陆麟瑞 @樊澄宇 @贾文卓 帮帮本蒟蒻


3
已采纳
樊澄宇
樊澄宇
新手光能
新手光能

动态规划

用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

 

 

求采纳 求采纳 求采纳

0
0
张睿杰
张睿杰
初级天翼
初级天翼

1217   数组接龙很像

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;
}

不对吗? @樊澄宇 

0
0
我要回答