This post is written in Chinese. Please consider using Google Translate

提供一个没有优化的O(N^2)的动态规划解法。首先对所有的演讲时间区间按结束时间从小到大排序，然后设定状态。

S[i].l和S[i].r分别表示第i个演讲的开始和结束时间。 F[i]为进行第i个演讲时已经使用了的最大的时间

状态转移方程 F[i] = Max{ F[j] | S[j].r <=S[i].l } + S[i].r - S[i].l

结果 Max { F[i] }

#include <iostream>
#include <stdlib.h>

using namespace std;

const int MAX=10001;

struct segment
{
    int l,r;
};

segment S[MAX];
int N,Ans;
int F[MAX];

int cmp(const void *a,const void *b)
{
    return ((segment *)a)->r - ((segment *)b)->r;
}

void init()
{
    int i;
    freopen("rez.in","r",stdin);
    freopen("rez.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d%d",&S[i].l,&S[i].r);
    }
    qsort(S+1,N,sizeof(S[0]),cmp);
}

void dynamic()
{
    int i,j;
    for (i=1;i<=N;i++)
    {
        for (j=N-1;j>=1;j--)
        {
            if (S[j].r<=S[i].l)
            {
                if (F[j]>F[i])
                {
                    F[i]=F[j];
                }
            }
        }
        F[i] += S[i].r - S[i].l;
        if (F[i]>Ans)
            Ans=F[i];
    }
}

int main()
{
    init();
    dynamic();
    cout << Ans;
    return 0;
}

阶梯教室设备利用

【问题描述】

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

任务：

请写一个程序：

•  在输入文件中读入所有演讲的起始和终止时间；

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

•  把结果写到输出文件中。

【输入文件】

在输入文件的第一行包括一个正整数 n ， n <= 10000 ，为所有的演讲的数目。

以下的 n 行每行含有两个由空格隔开整数 p 和 k ， 0 <= p < k <= 30000 。这样的一对整数表示一个演讲由时间 p 开始到时间 k 结束。

【输出文件】

输出文件只有唯一的一个整数，为最长的演讲总时间。

【样例输入】

rez.in

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


【样例输出】

rez.out

16