Official Analysis

It might be tempting at first to do a 2-dimensional DP with the number of computer purchases and the number of customer orders, but that would result in a nasty and inefficient transition.

Instead, let's try grouping the two into a single array of "transactions". Each transation has three attributes: the change in the number of cores, the associated clock rate of the cores, and the change in the total profits. For example, the example case would have a transaction array that looks like this:

Now we sort the array by clock rate in reverse, resulting in this:

Notice that in this order, as long as a customer order comes after a computer purchase, the computer will be able to satisfy the order as long as there are enough cores.

This drastically simplifies the problem. Now we can simply define $\texttt{max\_profits}[t][c]$ as the maximum profit we can gain from the first $t$ transactions given that we have $c$ cores left. Given this, the rest of the problem is simple knapsack.

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

struct Transaction {
	int cores;