程序填空题：求解会议安排问题（动态规划）

陈老师是一个比赛队的主教练。有一天，他想与团队成员开会，应该为这次会议安排教室。教室非常缺乏，所以教室管理员必须接受订单和拒绝订单以优化教室的利用率。如果接受一个订单，该订单的开始时间和结束时间成为一个活动。每个时间段只能安排一个订单（即假设只有一个教室）。请你找出一个最大化的总活动时间的方法。你的任务是这样的：读入订单，计算所有活动（接受的订单）占用时间的最大值。

```c++
#include
#include
#include
#include
#include
using namespace std;
#define MAX 101
//问题表示
struct NodeType
{
int b; //开始时间
int e; //结束时间
int length; //订单的执行时间
};

bool cmp(const NodeType &a,const NodeType &b)
{ //用于排序的运算符重载函数
return a.e}

int n; //订单个数
NodeType A[MAX]; //存放订单
//求解结果表示
int dp[MAX]; //动态规划数组
int pre[MAX]; //pre[i]存放前驱订单编号
void solve();

int main()
{
cin>>n;
for(int i=0;i cin>>A[i].b>>A[i].e;
for (int i=0; i A[i].length=A[i].e-A[i].b;
solve();
cout< return 0;
}

void solve() //求dp和pre
{
memset(dp,0,sizeof(dp)); //dp数组初始化
stable_sort(A,A+n,cmp); //采用稳定的排序算法
dp[0]=A[0].length;
pre[0]=-1;
for (int i=1;i {
int low=0, high=i-1;
while(low<=high) //在A[0..i-1]中查找结束时间早于A[i]开始时间的最晚订单A[low-1]
{
int mid=(low+high)/2;
if(A[mid].e<=A[i].b)
low=mid+1;
else
high=mid-1;
}
if (low==0) //特殊情况
{
if(dp[i-1]>=A[i].length)
{
dp[i]=;
pre[i]=-2; //不选中订单i
}
else
{
dp[i]=;
pre[i]=-1; //没有前驱订单
}
}
else //A[i]前面最晚有兼容订单A[low-1]
{
if (dp[i-1]>=dp[low-1]+A[i].length)
{
dp[i]=;
pre[i]=-2; //不选中订单i
}
else
{
dp[i]=;
pre[i]=low-1; //选中订单i
}
}
}
}
```
### 输入格式:

第一行是一个整数n，接着的n行中每一行包括两个整数b和e，其中b是一个订单开始时间，e是的结束时间。。

### 输出格式:

输出一行包括所有活动占用时间的最大值。

### 输入样例1:

```in
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 15
```

### 输出样例1:

```out
13
```





答案：
第1空：dp[i-1]

第2空：A[i].length

第3空：dp[i-1]

第4空：dp[low-1]+A[i].length