ข้อนี้มี Sushi ยาว $n$ $(n\leq 1000000)$ ที่สามารถตัดได้ที่ $m$ $(m\leq 20000)$ ตำแหน่ง คือที่ระยะ $R_1,R_2,\dots,R_m$ จากด้านซ้าย โดยจะแบ่งให้เพื่อน $k$ $(k\leq 20000)$ คน คนละหนึ่งชิ้นหลังตัด โดยคนที่ $i$ จะได้รับส่วนที่ $i$ จากด้านซ้ายเรียงกันหลังการตัด

เพื่อนคนที่ $i$ มีค่าความชอบ $P_i$ $(P_i \leq 1000)$ และจะได้รับความสุขเป็น $P_i$ คูณความยาวของชิ้นที่ได้รับ (ต้องได้ชิ้นที่มีความยาวมากกว่า $0$)

โจทย์ถามว่าจะได้ความสุขรวมมากที่สุดเท่าไหร่

Dynamic Programming

เพื่อความสะดวกกำหนดให้ $R_0=0, R_{m+1}=n$

ข้อนนี้สามารถมองเป็นโจทย์ Dynamic Programming โดยให้ $DP[i][j]$ แทนค่ารวมมากสุดที่เป็นไปได้หากแบ่ง Sushi แล้วถึง $R_i$ โดยคนที่ได้รับชิ้น $i$ คือเพื่อนที่ $j$

เราจะเริ่มจาก $DP[0][0] = 0$ เพราะยังไม่มีความสุขและยังไม่ได้ให้ Sushi ชิ้นใดกับเพื่อนคนไหน และ $DP[0][j] = -\infty$ เพราะไม่สามารถจบที่เพื่อนคนที่ $j$ โดยยังไม่มีใครได้สักชิ้น

จากนั้นสามารถพิจารณากรณี $i\geq 1$

สังเกตว่า $DP[i][1]$ จะเท่ากับ $R_i \times P_1$ เพราะเพื่อนถ้าคนแรกได้ถึง $R_i$ จะต้องได้ทั้งหมดตั้งแต่ $0$ ถึง $R_i$

สำหรับ $j>1$ จะสังเกตว่า $DP[i][j] = \max(DP[i-1][j-1], DP[i-1][j]) + (R_i - R_{i-1}) P_j$ เพราะถ้าจะจบการแบ่งถึง $R_i$ โดยให้เพื่อนคนที่ $j$ ชิ้นก่อนหน้าถึง $R_{i-1}$ จะต้องถูกแบ่งให้เพื่อนคนที่ $j$ หรือ $j-1$ เท่านั้น ซึ่งจะเป็น $\max(DP[i-1][j-1], DP[i-1][j])$ และการให้ช่วง $[R_{i-1},R_i]$ กับคนที่ $j$ จะได้ความสุข $(R_i - R_{i-1}) P_j$

เห็นได้ว่าการคำนวณแต่ละช่องของ $DP$ จะใช้เวลา $\mathcal{O}(1)$ มี $mk$ ช่องทั้งหมดจึงเป็น $\mathcal{O}(mk)$

อย่างไรก็ตามเนื่องจากข้อนี้ให้ Memory เพียง 16 Mb จะไม่สามารถประกาศ $DP$ ให้มี $mk$ ช่องโดยตรงจึงต้องหาวิธีลดการใช้ Memory

สังเกตว่าในการคำนวณ $DP_i[j] = DP[i][j]$ สำหรับ $i$ ใดๆ เราจะต้องใช้เพียง Array $DP_{i-1}$ เพราะในสูตรที่ใช้จะใช้เพียง $DP_{i-1}$ โดยไม่ต้องใช้ $DP_{1}, DP_2, \dots, DP_{i-2}$ ดังนั้น ณ เวลาใดๆ จะต้องเก็บอย่างมาก $2k$ ค่า ทำให้ลดการใช้ Memory เป็น $\mathcal{O}(k)$ โดยไม่เพิ่ม Time Complexity

ตัวอย่างโค้ด

#include <iostream>

using namespace std;

int R[20010];
int P[20010];

int DP[2][20010];
int main() {
  int n, m, k;
  cin >> n >> m >> k;

  for (int i = 1; i <= m; i++)
    cin >> R[i];
  R[m + 1] = n;

  for (int i = 1; i <= k; i++)
    cin >> P[i];

  DP[0][0] = 0;
  for (int i = 1; i <= m; i++)
    DP[0][i] = -1000000000;

  for (int i = 1; i <= m + 1; i++) {
    DP[i % 2][1] = R[i] * P[1];
    for (int j = 2; j <= k; j++)
      DP[i % 2][j] = max(DP[(i + 1) % 2][j], DP[(i + 1) % 2][j - 1]) + (R[i] - R[i - 1]) * P[j];
  }

  cout << DP[(m + 1) % 2][k];
}

ในโค้ดนี้จะใช้ DP[0] กับ DP[1] สลับกันโดย DP[i%2] จะใช้แทน $DP_i$ ในแต่ละขั้น และ DP[(i+1)%2] จะแทน $DP_{i-1}$