程序填空题：求解流水作业调度问题（回溯法）

有n个作业（编号为1～n）要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi（1≤i≤n）。
流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。

```c++
#include
#include
#include
#include
#define INF 0x3f3f3f3f //最大整数∞
#define MAX 1001 //最多的作业数
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n; //作业数
int a[MAX]={0}; //M1上的执行时间,不用下标0的元素
int b[MAX]={0}; //M2上的执行时间,不用下标0的元素
int bestf; //存放最优调度时间
int f1; //M1的执行时间
int f2[MAX]; //M2的执行时间
int x[MAX]; //当前调度方案
int bestx[MAX]; //存放当前作业最佳调度
void swap(int &x,int &y) //交换x和y
{ int tmp=x; x=y; y=tmp;}

void disparr(int x[]) //输出一个数组的元素
{ for (int i=1;i<=n;i++)
printf("%d ",x[i]);
}

void dfs(int i) //从第i层开始搜索
{ if (i>n) //到达叶结点,产生一种调度方案
{ if (f2[n] {;
for(int j=1; j<=n; j++) //复制解向量
;
}
}
else
{ for(int j=i; j<=n; j++) //没有到达叶结点,考虑i到n的作业
{ f1 += a[x[j]]; //在第i层选择执行作业x[j],在M1上执行完的时间
f2[i]=;
if () //剪枝:仅仅扩展当前总时间小于bestf的结点
{ swap(x[i],x[j]);
dfs(i+1);
;
}
f1 -= a[x[j]]; //回溯，即撤销第i层对作业x[j]的选择,以便再选择其他作业
}
}
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
f1=0;
bestf=INF;
memset(f2,0,sizeof(f2));
for(int k=1; k<=n; k++) //设置初始调度为作业1,2,…,n的顺序
x[k]=k;
dfs(1); //从作业1开始搜索
printf("%d\n",bestf);
disparr(bestx);
return 0;
}
```

### 输入格式:

第一行输入作业数n，接着的n行分别为在M1和M2加工各作业所需的时间。

### 输出格式:
先输出所需加工时间，再输入最优调度方案。

### 输入样例1:

```in
4
5 6
12 2
4 14
8 7
```

### 输出样例1:

```out
33
3 1 4 2
```





答案：
第1空： bestf=f2[n]

第2空：bestx[j] = x[j]

第3空：max(f1,f2[i-1])+b[x[j]]

第4空：f2[i]
第5空：swap(x[i],x[j])