Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i > 0$, let $\text{p}[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: $$\text{p}[1] = 1, \text{p}[2] = 5, \text{p}[3] = 8, \text{p}[4] = 9, \text{p}[5] = 10, \text{p}[6] = 17, \text{p}[7] = 18$$ Which of the following statements is/are correct about $R_7$?

We can compute $R_n$ for $n = 1, 2, \dots, 7$ using the dynamic programming recurrence:

Evaluating iteratively:

• $R_1 = \text{p}[1] = 1$

• $R_2 = \max(\text{p}[2], \text{p}[1] + R_1) = \max(5, 1+1) = 5$

• $R_3 = \max(\text{p}[3], \text{p}[1] + R_2, \text{p}[2] + R_1) = \max(8, 1+5, 5+1) = 8$

• $R_4 = \max(\text{p}[4], \text{p}[1] + R_3, \text{p}[2] + R_2, \text{p}[3] + R_1) = \max(9, 1+8, 5+5, 8+1) = 10$

• $R_5 = \max(\text{p}[5], \text{p}[1] + R_4, \text{p}[2] + R_3, \text{p}[3] + R_2, \text{p}[4] + R_1) = \max(10, 1+10, 5+8, 8+5, 9+1) = 13$

• $R_6 = \max(\text{p}[6], \text{p}[1] + R_5, \text{p}[2] + R_4, \text{p}[3] + R_3, \text{p}[4] + R_2, \text{p}[5] + R_1) = \max(17, 1+13, 5+10, 8+8, 9+5, 10+1) = 17$

• $R_7 = \max(\text{p}[7], \text{p}[1] + R_6, \text{p}[2] + R_5, \text{p}[3] + R_4, \text{p}[4] + R_3, \text{p}[5] + R_2, \text{p}[6] + R_1) = \max(18, 1+17, 5+13, 8+10, 9+8, 10+5, 17+1) = 18$

Thus, $R_7 = 18$, so A is correct and B is incorrect.

Now find all integer partitions of $7$ that yield total revenue equal to $18$:

1. A single piece of length $7$: $\text{p}[7] = 18$

2. Two pieces of lengths $1$ and $6$: $\text{p}[1] + \text{p}[6] = 1 + 17 = 18$

3. Three pieces of lengths $2, 2,$ and $3$: $\text{p}[2] + \text{p}[2] + \text{p}[3] = 5 + 5 + 8 = 18$

Hence, $R_7$ is achieved by exactly three distinct multiset cuts, making C correct and D incorrect (since $\{2, 2, 3\}$ consists of $3$ pieces).