คำอธิบายวิธีทำพร้อม Code สำหรับข้อ toi20_lover

---

Problem

สรุปโจทย์

มีร้านอาหารทั้งหมด \(N\) ร้าน (โดยที่ \(N\) เป็น เลขคู่)
ร้านที่ \(i\) มีราคาเท่ากับ \(x_i\)

เราต้องแบ่งช่วงการกินข้าวออกเป็นหลายช่วง สมมติว่ามี \(M\) ช่วง โดยต้องให้

\[ l_1 + l_2 + \cdots + l_M = N \]

และในแต่ละช่วง \(j\)
จำนวนร้านที่กินในช่วงนั้น \(l_j\) ต้องเป็น เลขคู่

ช่วงการกินแต่ละช่วงจะครอบคลุมร้านตามลำดับ เช่น

• ช่วงที่ 1: ร้านที่ \(1\) ถึง \(l_1\)
• ช่วงที่ 2: ร้านที่ \(l_1 + 1\) ถึง \(l_1 + l_2\)
• ช่วงที่ \(j\): ร้านที่ \(l_1 + l_2 + \cdots + l_{j-1} + 1\) ถึง \(l_1 + l_2 + \cdots + l_j\)

โดยในแต่ละช่วง จะมีการ “กิน” 2 รอบ:

1. รอบแรก — กินร้านครึ่งแรกของช่วง (จากร้าน \(p\) ถึงร้าน \(\frac{p + q - 1}{2}\))
   และกินเฉพาะร้านที่มีราคาเป็น เลขคี่
2. รอบที่สอง — กินร้านครึ่งหลังของช่วง (จากร้าน \(\frac{p + q - 1}{2} + 1\) ถึงร้าน \(q\))
   และกินเฉพาะร้านที่มีราคาเป็น เลขคู่

ให้: - \(a_j =\) ผลรวมราคาที่กินในรอบแรกของช่วงที่ \(j\) - \(b_j =\) ผลรวมราคาที่กินในรอบที่สองของช่วงที่ \(j\)

โดยต้องมีเงื่อนไขว่า

\[ \max(a_1, a_2, \dots, a_M) \leq V \]

และ

\[ \max(b_1, b_2, \dots, b_M) \leq W \]

จงหาว่า \(M\) มีค่าต่ำสุดเท่าไร

Constraints

• \(2 \leq N \leq 10^4\)
• \(1 \leq V, W \leq 10^9\)
• \(1 \leq x_i \leq 10^4\)

Prerequisites

• Dynamic Programming
• Prefix Sum

---

Solution

ไอเดียหลัก

สังเกตได้ว่าเงื่อนไข \(imax(c_1, c_2, \dots, c_K) \leq D\)
หมายความว่า \(c_j \leq D\) สำหรับทุก ๆ \(j\)

ดังนั้นเราจะนิยามว่า
\(dp[n] =\) จำนวนช่วงที่น้อยที่สุด โดยพิจารณาแค่ร้าน \(n\) ร้านแรก
และช่วงสุดท้ายจบที่ร้านที่ \(n\)

เราจะได้ว่า

\[ dp[n] = \min_{\substack{i < n,\\ (n - i) \equiv 0 \pmod{2}\\ \text{โดยที่ผลรวมรอบแรก} \leq V,\\ \text{ผลรวมรอบสอง} \leq W}} (dp[i] + 1) \]

---

การคำนวณผลรวม

ให้: - \(p_{odd}[j] =\) ผลรวมราคาของร้านที่มีราคาเป็น เลขคี่ เมื่อพิจารณา \(j\) ร้านแรก
- \(p_{even}[j] =\) ผลรวมราคาของร้านที่มีราคาเป็น เลขคู่ เมื่อพิจารณา \(j\) ร้านแรก

เราจะให้ \(mid = \dfrac{n + i}{2}\)

จากนั้น:

• รอบแรก: ต้องมี
  \(p_{odd}[mid] - p_{odd}[i] \leq V\)
• รอบสอง: ต้องมี
  \(p_{even}[n] - p_{even}[mid] \leq W\)

ทั้งสองค่าตรวจสอบได้ใน \(O(1)\)

เนื่องจากเราต้องเช็กทุก ๆ \(i < n\) ที่ \((n - i)\) เป็นเลขคู่
จึงได้ time complexity รวมเป็น \(O(N^2)\)

---

Code

toi20_lover.cpp

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int inf = 1e9;

int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n, v, w; cin >> n >> v >> w;
    vector<int> a(n + 1), p_odd(n + 1), p_even(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p_odd[i] = p_odd[i - 1];
        p_even[i] = p_even[i - 1];
        if (a[i] % 2) p_odd[i] += a[i];
        else p_even[i] += a[i];
    }
    vector<int> dp(n + 1, inf); dp[0] = 0;
    for (int r = 2; r <= n; r += 2) {
        for (int l = r - 2; l >= 0; l -= 2) {
            int mid = (l + r) / 2;
            int vs = p_odd[mid] - p_odd[l],
                ws = p_even[r] - p_even[mid];
            if (vs <= v && ws <= w) dp[r] = min(dp[r], dp[l] + 1);
        }
    }
    cout << (dp[n] == inf ? -1 : dp[n]);
}

Total Time Complexity

\(O(N^2)\)