อธิบายโจทย์เพิ่มเติม

จากโจทย์ ความอร่อยของไส้อั่วชิ้นที่ $i$ คือ $D_{i}$

กำหนดให้ $l$ หมายถึงปลายฝั่งซ้ายของไส้อั่ว และ $r$ หมายถึงปลายฝั่งขวาของไส้อั่ว

ในการกินไส้อั่วแต่ละครั้งต้องกินส่วนปลายเท่านั้น ไม่ว่าจะเป็นทางซ้ายหรือทางขวา โดยเมื่อกินแต่ละครั้งจะได้ความอร่อยทิพย์ $|D_l - D_r|$

โดยความอร่อยในการกินแต่ละครั้งจะมีค่าเท่ากับ ความอร่อยของไส้อั่วชิ้นที่เลือก บวกกับ ความอร่อยทิพย์ครั้งก่อนหน้า สามารถเขียนเป็นสมการได้เป็น

$Del_{now} = Del_{prev} + D_{choose}$

เมื่อ $Del$ หมายถึง ความอร่อยทั้งหมด(รวมทั้งความอร่อยทิพย์) ที่สามารถกินได้ เมื่อพิจารณาช่วง $l$ ถึง $r$

แต่ทว่าในการก่อนการกินแต่ละครั้งสามารถเลือกที่จะตัดไส้อั่วก่อนได้ และในบางครั้งการตัดไส้อั่วจะทำให้ความอร่อยรวมทั้งหมดนั้นเพิ่มขึ้น

โดยในการกินทั้งหมดต้องการทำให้ผลรวมความอร่อยทั้งหมดมากที่สุด

กลุ่มชุดสอบที่ไม่มีการตัดไส้อั่ว (12 คะแนน)

เนื่องจากในชุดทดสอบนี้ไม่มีการตัดไส้อั่ว ทำให้จำเป็นต้องคิดเพียงการหา $Del_{now}$ เท่านั้น

นิยาม $dp(l, r)$ หมายถึง ความอร่อยมากที่สุดที่สามารถกินได้ในช่วง $l$ ถึง $r$ โดยไม่มีการตัดไส้อั่ว

โดย $Del_{now}$ จะมีค่าเท่ากับ $dp(l, r)$ และ $Del_{prev}$ จะมีค่าได้ 2 แบบคือ

• เลือกฝั่งซ้ายจะทำให้ $Del_{prev} = dp(l + 1, r)$
• เลือกฝั่งขวาจะทำให้ $Del_{prev} = dp(l, r - 1)$

และในการเลือกกินแต่ละครั้งจะเลือกฝั่งที่มีค่ามากที่สุดเพื่อให้ในการกินแต่ละครั้งความอร่อยจะมากที่สุดเท่าที่เป็นไปได้ ดังนั้นสามารถเขียนเป็นสมการได้เป็น

Time Complexity : $O(N^{2})$

สุดท้ายคำตอบจะอยู่ที่ $dp(1, N)$ เนื่องจาก $dp(l, r)$ เป็นคำตอบในช่วง $l$ ถึง $r$ เช่นกัน

กลุ่มชุดสอบที่ $N\le1\,000$ (65 คะแนน)

ในชุดทดสอบกลุ่มนี้สามารถใช้ Matrix Chain Multiplication ในการลองไล่ตัดทุกวิธีได้

นิยาม $opt(l, r)$ หมายถึง ความอร่อยมากที่สุดที่สามารถกินได้ในช่วง $l$ ถึง $r$ โดยมีการตัดกี่ครั้งก็ได้

ในการพิจารณาแต่ละ $l, r$ จะตัดที่จุด $k$ ทำให้แบ่งไส้อั่วได้ 2 ชิ้นเป็น $l$ ถึง $k$ และ $k + 1$ ถึง $r$

Time Complexity : $O(N^{3})$

สุดท้ายคำตอบจะอยู่ที่ $opt(1, N)$ เนื่องจาก $opt(l, r)$ เป็นความอร่อยที่มากที่สุดเมื่อสามารถตัดกี่ครั้งก็ได้ในช่วง $l$ ถึง $r$

ไม่มีเงื่อนไขเพิ่มเติม (100 คะแนน)

ในปัญหาย่อยนี้ต้อง optimize การหา $opt(l, r)$ ที่เป็นปัญหา Matrix Chain Multiplication ลงให้ใช้เวลาไม่เกิน $O(N^{2})$

ตั้งนิยามใหม่ให้กับ $opt$ โดย นิยาม $opt(r)$ หมายถึง ความอร่อยมากที่สุดที่สามารถกินได้ในช่วง $l$ ถึง $r$ โดยมีการตัดกี่ครั้งก็ได้ เมื่อ $l \le r$

Time Complexity : $O(N^{2})$

สุดท้ายคำตอบจะอยู่ที่ $opt(N)$ เนื่องจาก $opt(N)$ เป็นความอร่อยที่มากที่สุดเมื่อสามารถตัดกี่ครั้งก็ได้ในช่วง $1$ ถึง $N$

#include <bits/stdc++.h>
using namespace std;
const int MxN = 5050;
int n, dp[MxN][MxN], opt[MxN], D[MxN];
int main() {
  cin.tie(nullptr)->ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> D[i];
  }
  for (int i = 1; i <= n; ++i) {
    dp[i][i] = D[i];
  }
  for (int sz = 2; sz <= n; ++sz) {
    for (int l = 1; l + sz - 1 <= n; ++l) {
      int r = l + sz - 1;
      dp[l][r] =
          abs(D[l] - D[r]) + max(dp[l + 1][r] + D[l], dp[l][r - 1] + D[r]);
    }
  }
  for (int r = 1; r <= n; ++r) {
    opt[r] = dp[1][r];
    for (int l = 1; l < r; ++l) {
      opt[r] = max(opt[r], opt[l] + dp[l + 1][r]);
    }
  }
  cout << opt[n];
  return 0;
}