Suppose you are consulting for a company that manufactures computer equipment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply s_i of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each weeks supply can be carried by one of two air freight companies, A or B.

Company A charges at a fixed rate r per pound (so it costs rs_i to ship a weeks supply s_i).

Company B makes contracts for a fixed amount c per week, independent of weight. However, contracts with company B must be made in blocks of four consecutive weeks at a time.

A schedule for the computer company is a choice of air freight company (A or B) for each of the n weeks with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks in time. The cost of the schedule is the total amount paid to companies A and B, according to the description above.

We seek a way in polynomial-time to take in a sequence of supply values s₁, ..., s_n and return a schedule of minimum cost. For example, suppose r = 1, c = 10, and the sequence of values is

11, 9, 9, 12, 11, 12, 12, 9, 9, 11.

Then the optimal schedule would be to chose company A for the first three weeks, company B for the next block of four contiguous weeks, and then company A for the final three weeks. One way to do this is set up the Bellman equation, then let a solver get the answer in polynomial time.

For this problem, derive the Bellman equation, and talk through how you derived it. You must write down your Bellman equation, and you must sufficiently explain your rationale to get credit for this problem.