用2 台处理机A 和B 处理n个作业。设第i 个作业交给机器A 处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性 能关系，很可能对于某些i，有ai>=bi，而对于某些j，j≠i，有aj<bj，既不能将一个作业分开由2 台机器处理，也没有一台机器能 同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。

input
6
2 5 7 10 5 2
3 8 4 11 3 4
output15

//独立任务调度

#include<iostream>
#include<vector>
using namespace std;

const int n=6;
int a1[]={2,5,7,10,5,2};
int b1[]={3,8,4,11,3,4};

class tree
{
public:
int a,b;

};

int main()
{
cout<<“******************************************”<<endl;
cout<<”         任务调度情况如下:”<<endl;
cout<<”       (1)作业数目:”<<n<<endl;
cout<<”       (2)各作业处理时间:”<<endl;
cout<<”       “;
for(int aj=0;aj<n;aj++)
cout<<a1[aj]<<” “;
cout<<endl;
cout<<”       “;
for(int bj=0;bj<n;bj++)
cout<<b1[bj]<<” “;
cout<<endl;
cout<<“******************************************”<<endl<<endl;
cout<<“最优处理时间为:”;
vector<tree *> w;
tree *k=new tree;
k->a=a1[0];
k->b=0;
w.push_back(k);
k=new tree;
k->a=0;
k->b=b1[0];
w.push_back(k);
w.push_back(0);

int poi=0;
int top=0;
while(top<n-1)
{
if(w[poi])
{
k=new tree;
k->a=w[poi]->a+a1[top+1];
k->b=w[poi]->b;
w.push_back(k);
k=new tree;
k->a=w[poi]->a;
k->b=w[poi]->b+b1[top+1];
w.push_back(k);
poi++;

}
else
{
w.push_back(0);
poi++;
top++;

}

}
int q=10000000,j;
while(w[poi])
{
if(w[poi]->a>w[poi]->b)
j=w[poi]->a;
else
j=w[poi]->b;
if(j<q)
q=j;
poi++;
}
cout<<q<<endl;
for(int i=0;i<w.size();i++)
if(w[i])
delete w[i];
cout<<endl;
return 0;
}