Suppose you are managing a consulting team of expert computer hackers, and each week you have to choose a job for them to undertake.

Suppose you are managing a

consulting team of expert computer hackers, and each week you have to

choose a job for them to undertake. The set of possible jobs is divided

into those that are low-stress (e.g. setting up a Web site for a class at the

local elementary school) and those that are high-stress (e.g., protecting the

dean's most valuable secrets.) The basic question each week is whether to

take on a low-stress job or a high-stress job.

If you select a low-stress job for your team in week i, then you get a revenue

of li > 0 dollars; if you select a high-stress job, you get a revenue of hi > 0

dollars. High-stress jobs typically pay more. The catch, however, is that

in order for the team to take on a high-stress job in week i, it is required

that they do no job (of either type) in week i????1; they need a full week of

prep time to get ready for the crushing stress level. On the other hand, it

is okay for them to take a low-stress job in week i even if they have done a

job (of either type) in week i????1. So, given a sequence of n weeks, a plan

is specied by a choice of low-stress, high-stress or none for each of the n

weeks, with the property that if high-stress is chosen for week i > 1, then

none has to be chosen for week i ???? 1. (It is okay to choose a high-stress

job in week 1.) The value of the plan is determined in the natural way;

for each i, you add li to the value if you choose low-stress in week i, and

you add hi to the value if you choose high-stress in week i. (You add 0 if

you choose none in week i.)

Given sets of values l1; l2; :::; ln and h1; h2; :::; hn, nd a plan of maximum

value (such a plan is called optimal.) Give an ecient algorithm to take

the input values and return the value of an optimal plan.