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

สรุปโจทย์

มี $N$ ร้าน($N$ เป็นเลขคู่) โดยร้านที่ $i$ มีราคา $x_i$

โดยต้องแบ่งช่วงการกินข้าวเป็นช่วงๆ สมมติว่ามี $M$ ช่วง โดยต้องให้ $l_1+l_2+\cdots+l_M=N$ และ $l_j$ คือจำนวนร้านที่กินในช่วงการกินข้างที่ $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$

สมมติให้ช่วงการกินที่ $j$ กินจากร้านที่ $p$ ไปร้านที่ $q$ โดยช่วงการกินจะแบ่งเป็น $2$ รอบ รอบแรกจะกินร้านที่ $p$ จนถึงร้านที่ $\frac{p+q-1}{2}$ และกินเฉพาะร้านที่มีราคาเป็นเลขคี่ รอบที่สองจะกินจากร้านที่ $\frac{p+q-1}{2}+1$ จนถึงร้านที่ $q$ และกินเฉพาะร้านที่มีราคาเป็นเลขคู่

ให้ผลรวมราคาที่กินไปของรอบแรกของช่วงที่ $j$ เป็น $a_j$ และให้ผลรวมราคาของรอบที่สองที่กินไปของช่วงที่ $j$ เป็น $b_j$ เราต้องให้ $\max(a_1,a_2,\cdots,a_M)\leq V$ และ $\max(b_1,b_2,\cdots,b_M)\leq W$

ให้หาว่า $M$ มีค่าน้อยสุดคือเท่าไหร่

Prerequisites

• Dynamic Programming
• Prefix Sums

ขอบเขตข้อมูล

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

วิธีทำ

สังเกตได้ว่าการที่ $\max(c_1,c_2,\cdots,c_K)\leq D$ แปลว่า $c_j \leq D$ สำหรับทุกๆ $1\leq j\leq K$

จะได้ว่าถ้าให้ $dp[n]=$ ค่า $M$ ที่น้อยที่สุดโดยที่คิดแค่ $n$ ร้านแรก และช่วงการกินช่วงสุดท้ายจบที่ร้านที่ $n$ สังเกตได้ว่า $\displaystyle dp[n]=\max_{\substack{i<n,\space n-i \space \equiv \space 0 \pmod 2\\ \text{โดยที่ผลรวมราคาที่กินไปของรอบแรก}\leq V\\ \text{โดยที่ผลรวมราคาที่กินไปของรอบที่สอง}\leq W}}dp[i]+1$

ถ้าเราให้ $p_{odd}[j]=$ ผลรวมของทุกๆ ราคาเมื่อราคาเป็นเลขคี่เมื่อคิดแค่ $j$ ร้านแรก และ $p_{even}[j]=$ ผลรวมของทุกๆ ราคาเมื่อราคาเป็นเลขคู่เมื่อคิดแค่ $j$ ร้านแรก

เราจะให้ $mid=\frac{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 \space \equiv \space 0 \pmod 2$ สำหรับ $dp[n]$ ซึ่งต้องเช็ค $O(N)$ จุด แล้วเราต้องทำ $dp[n]$ สำหรับทุกๆ $n<N$ จะได้ว่าเวลารวมที่จำเป็นต้องใช้คือ $O(N^2)$

Solution Code:

#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]);
}

Time Complexity: $O(N^2)$

หากมีข้อสงสัย comment ไว้ใต้ post ได้เลยนะครับ 🙇‍♂️🙇‍♂️
ศึกษาโจทย์เพิ่มเติมได้ที่ Fast X Fourier