Món Ăn (DPRCMA)
Đề bài
DPRCMA – Món ăn
SẮN đã mua $N$ món ngon tuyệt vời cho những con bò, bán cho chúng để nhận lại tiền. SẮN bán một món ăn mỗi ngày và muốn tối đa hóa số tiền anh ta nhận được. Các món ăn rất thú vị vì nhiều lý do:
- Các món ăn được đánh số $1..N$ và được lưu tuần tự trong một hộp dài mở ở hai đầu. Vào bất cứ ngày nào, SẮN chỉ có thể lấy một món ăn từ một trong hai đầu của hộp.
- Giống như rượu vang hảo hạng và pho mát ngon, các món ăn được cải thiện theo tuổi tác và ra giá cao hơn.
- Các món ăn có chất lượng không đồng nhất: một số tốt hơn và có giá trị cao hơn. Món thứ $i$ có giá trị $v[i]$.
- Bò trả nhiều tiền hơn cho các món ăn đã có tuổi lâu hơn: một con bò sẽ trả $v[i] \cdot a$ cho một món ăn có tuổi $a$.
Với các giá trị $v[i]$ của mỗi món ăn đã được xếp tuần tự trong hộp mở hai đầu, hỏi giá trị lớn nhất mà SẮN có thể nhận được là gì nếu anh ta bán các món ăn một cách tối ưu? Món đầu tiên được bán vào ngày 1 và có tuổi $a = 1$. Mỗi ngày tiếp theo tăng tuổi lên 1.
Dữ liệu vào:
- Dòng 1: Một số nguyên duy nhất là $N$.
- Dòng $2..N + 1$: Dòng $i + 1$ chứa giá trị của món ăn thứ $i$ là $v[i]$.
Kết quả: Doanh thu tối đa SẮN có thể đạt được bằng cách bán các món ăn.
Ràng buộc: $1 \le N \le 2000$, $1 \le v[i] \le 1000$.
5
1 3 1 5 243Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là một bài quy hoạch động trên đoạn rất kinh điển, mình sẽ đi từ vét cạn, lên đệ quy có nhớ, rồi bottom-up và cuối cùng là rút gọn còn mảng 1 chiều để các bạn thấy cả quá trình nha.
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau. Bạn có $n$ món ăn ($1 \le n \le 2000$) được xếp tuần tự trong 1 hộp dài mở hai đầu; mỗi lần bạn chỉ có thể lấy 1 món ăn từ 1 trong 2 đầu của hộp. Món thứ $i$ có giá trị $v[i]$ ($1 \le v[i] \le 1000$). Món được lấy đầu tiên có tuổi là 1, món được lấy lần thứ 2 có tuổi là 2, …, món cuối cùng (lần lấy thứ $n$) có tuổi là $n$. Bán một món thì được số tiền là $v[i] \times$ tuổi của nó (lần nó được lấy). Hỏi ta lấy các món ăn theo thứ tự nào để bán được nhiều tiền nhất, in ra số tiền đó.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ: $n = 5$, $v = \{1, 3, 1, 5, 2\}$, đáp án là $43$.
tráimón 11món 23món 31món 45món 52đầu
phải
Tổng số tiền kiếm được là $1 + 4 + 9 + 4 + 25 = 43$. Ý là món nào giá trị càng cao thì càng nên để dành bán sau (tuổi cao nhân hệ số lớn), nhưng vì chỉ lấy được ở 2 đầu nên không phải lúc nào cũng xếp được như ý, phải tính toán cẩn thận.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn bằng đệ quy – O(2^n)
Cách làm đơn giản nhất của bài này chính là vét cạn, nghĩa là ta sẽ thử mọi trường hợp có thể. Ta thấy rằng mỗi lần ta chỉ có thể lấy ở đầu hộp hoặc cuối hộp, hay chính là ở mỗi bước ta có 2 lựa chọn: chọn món ở đầu trái hay ở đầu phải. Từ đó ta xây dựng hàm đệ quy như sau:
- Hàm:
Try(int l, int r, int t)trả về số tiền tối đa kiếm được từ việc bán các món từ $l$ (left) tới $r$ (right), với món đầu tiên ta bán trong đoạn $[l, r]$ có tuổi là $t$ (time). - Điều kiện dừng: khi chỉ còn 1 món thì số tiền kiếm được = giá trị món đó × tuổi của nó. Khi $l = r$ thì chỉ còn 1 món, vậy
if(l == r) return v[l] * t; - Xử lý chạy: trong đoạn $[l, r]$ ta chỉ có thể lấy món thứ $l$ hoặc món thứ $r$:
- Lấy món thứ $l$: được $v[l] \cdot t$, đoạn còn lại là $[l + 1, r]$ và món đầu tiên bán trong đoạn đó có tuổi $t + 1$. Tổng tối đa là
v[l] * t + Try(l + 1, r, t + 1). - Lấy món thứ $r$: được $v[r] \cdot t$, đoạn còn lại là $[l, r - 1]$, tuổi tiếp theo $t + 1$. Tổng tối đa là
v[r] * t + Try(l, r - 1, t + 1).
return max(v[l] * t + Try(l + 1, r, t + 1), v[r] * t + Try(l, r - 1, t + 1)); - Lấy món thứ $l$: được $v[l] \cdot t$, đoạn còn lại là $[l + 1, r]$ và món đầu tiên bán trong đoạn đó có tuổi $t + 1$. Tổng tối đa là
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2005;
ll v[N];
ll Try(int l, int r, int t){
if(l == r){
return v[l] * t;
}
return max(v[l] * t + Try(l + 1, r, t + 1), v[r] * t + Try(l, r - 1, t + 1));
}
int main(){
// freopen("dprcma.inp", "r", stdin);
// freopen("dprcma.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i];
}
cout << Try(1, n, 1);
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
v = [0] + [int(x) for x in data[1:n + 1]]
def Try(l, r, t):
if l == r:
return v[l] * t
return max(v[l] * t + Try(l + 1, r, t + 1), v[r] * t + Try(l, r - 1, t + 1))
print(Try(1, n, 1))Giải thích 1 số chỗ trong code ở trên:
const int N = 2005;đây là giá trị $n$ tối đa, nó sẽ là 2000 nhưng mình thường cộng thêm 5 vào để khai báo mảng cho chắc.cout << Try(1, n, 1);ta cần tìm số tiền tối đa kiếm được từ món thứ nhất ($l = 1$) tới món thứ $n$ ($r = n$) với món đầu tiên bán có tuổi là 1 ($t = 1$).- Code gốc của mình có 2 dòng
freopen("dprcma.inp", ...)/freopen("dprcma.out", ...)để đọc ghi file. Khi nộp trên CLUE OJ (đọc/ghi chuẩn) thì các bạn để chúng ở dạng chú thích như trên là được; nếu đề thi yêu cầu đọc ghi file thì bỏ dấu//đi nhé. Đề ghi mỗi giá trị trên 1 dòng nhưng ví dụ lại để cùng 1 dòng;cinđọc kiểu nào cũng được nên không sao.
Trong khung chạy tay, để ý phần "Mỗi đoạn [l, r] đã bị gọi bao nhiêu lần": cùng một đoạn bị tính lại nhiều lần – đó là chỗ ta sẽ cải tiến ở cách 2.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$, vì ta chỉ dùng 1 mảng $v$ (cộng thêm độ sâu đệ quy tối đa $n$).
- Thời gian: $O(2^n)$. Vì mỗi lần ta có 2 lựa chọn, tổng cộng ta có $n$ lần chọn, nên có cỡ $2^n$ cách chọn và cần cỡ $2^n$ phép tính.
Cách 2Đệ quy có nhớ (quy hoạch động top-down) – O(n²)
Thứ khiến hàm Try() chạy lâu chính là: một trường hợp đã tính rồi, lần sau gặp lại ta lại đi tính lại. Ta cải tiến thành đệ quy có nhớ bằng cách nhìn xem những tham số của hàm Try() (tức $l$, $r$, $t$) tham số nào thay đổi khi gọi đệ quy. Cả $l$, $r$ và $t$ đều thay đổi, vậy ta cần một mảng 3 chiều với $F[l][r][t]$ lưu kết quả Try(l, r, t).
Nhưng $l$, $r$, $t$ tối đa đều có thể bằng $n = 2000$, mảng 3 chiều sẽ có $2000^3 = 8 \cdot 10^9$ phần tử = 8 tỉ phần tử! Ta không thể tạo một mảng hay vector to như thế được: riêng việc tạo mảng và gán giá trị ban đầu đã đủ TLE rồi, chưa kể còn quá giới hạn bộ nhớ.
Kiểm tra nhanh: lúc đầu $l = 1, r = n$ thì $t = n - n + 1 = 1$ ✓. Khi $l = r$ (món cuối cùng) thì $t = n$ ✓. Vậy hàm Try() chỉ còn 2 tham số $l$ và $r$ (khai báo $n$ là biến toàn cục để dùng trong hàm), khi $l = r$ thì trả về v[l] * n, và đáp án là Try(1, n).
Giờ ta chỉ cần mảng 2 chiều $F[l][r]$ lưu kết quả Try(l, r), kích thước $2000^2 = 4 \cdot 10^6$ phần tử – hoàn toàn tạo được. Mảng $F[N][N]$ khai báo toàn cục nên mặc định mọi phần tử bằng $0$. Và $0$ cũng là giá trị mà Try(l, r) không thể trả về (vì $v[i] \ge 1$ nên kết quả nhỏ nhất cũng là 1). Từ đó sau điều kiện dừng, ta kiểm tra f[l][r] != 0: nếu đúng thì đã tính rồi, trả về luôn; còn chưa thì tính, lưu vào f[l][r] rồi trả về.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2005;
int n;
ll v[N];
ll f[N][N];
ll Try(int l, int r){
if(l == r){
return v[l] * n;
}
if(f[l][r]){
return f[l][r];
}
int t = n - r + l;
return f[l][r] = max(v[l] * t + Try(l + 1, r), v[r] * t + Try(l, r - 1));
}
int main(){
// freopen("dprcma.inp", "r", stdin);
// freopen("dprcma.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i];
}
cout << Try(1, n);
return 0;
}import sys
import threading
def main():
data = sys.stdin.read().split()
n = int(data[0])
v = [0] + [int(x) for x in data[1:n + 1]]
f = [[0] * (n + 2) for _ in range(n + 2)]
def Try(l, r):
if l == r:
return v[l] * n
if f[l][r]:
return f[l][r]
t = n - r + l
f[l][r] = max(v[l] * t + Try(l + 1, r), v[r] * t + Try(l, r - 1))
return f[l][r]
print(Try(1, n))
sys.setrecursionlimit(10000)
threading.stack_size(256 * 1024 * 1024)
threading.Thread(target=main).start()Giải thích 1 số chỗ trong code ở trên:
if(f[l][r])ở đây chính là kiểm traif(f[l][r] != 0)đó anh em.return f[l][r] = max(...);đây chính là gánf[l][r] = max(…)rồi sau đóreturn f[l][r].- Bản Python cần đệ quy sâu tới $n = 2000$ tầng nên mình tăng giới hạn đệ quy và chạy trong một
threadcó stack lớn cho chắc ăn.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N^2)$. Thực chất là $O(N^2 + N)$ nhưng theo quy tắc Big-O thì là $O(N^2)$.
- Thời gian: $O(N^2)$. Trường hợp xấu nhất là phải lấp đầy nửa trên của bảng $F$, mỗi ô tính $O(1)$, tức khoảng $2000^2 / 2 = 2 \cdot 10^6$ ô. Vậy code chạy hoàn toàn dưới 1 giây.
Với cách làm trên là ta đã AC bài này rồi. Giờ ta sẽ đến với cách khác và có thể cải tiến hơn.
Cách 3Quy hoạch động bottom-up – O(n²)
Giờ ta sẽ đến với cách quy hoạch động bottom-up, chính là cách mà anh em sẽ tạo ra công thức truy hồi đó. Cho ae nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:
Bước 1: Xác định bài toán con
Gọi $F[i][j]$ là số tiền tối đa kiếm được từ việc bán các món từ $i$ tới $j$, với tuổi của món đầu tiên bán trong khoảng đó là $t = n - j + i$ (chính là $n$ – right + left đó anh em). Các món nằm ngoài khoảng $[i, j]$ thì ta coi như đã bán rồi nha.
Bước 2: Xác định bài toán cơ sở
Như điều kiện dừng của phần đệ quy: khi $i = j$ thì đó là món cuối cùng nên có tuổi $t = n$, giá trị nhận được là $v[i] \cdot n$. Vậy ta gán $F[i][i] = v[i] \cdot n$ với $i$ chạy từ 1 tới $n$.
Bước 3: Xác định đáp án của bài toán
Ta cần số tiền tối đa bán các món từ 1 tới $n$ với tuổi $t = 1 = n - n + 1$. Vậy kết quả hiển nhiên là $F[1][n]$.
Bước 4: Xác định công thức truy hồi
Rút từ cách đệ quy: ở cách 2 ta có Try(l, r) = max(v[l] * t + Try(l + 1, r), v[r] * t + Try(l, r - 1)). Thay $l = i$, $r = j$, Try(l + 1, r) $= F[i+1][j]$, Try(l, r - 1) $= F[i][j-1]$, ta được ngay công thức truy hồi.
Chứng minh trực tiếp (trong trường hợp bạn không làm cách vét cạn): xét các món trong đoạn từ $i$ tới $j$, ta có 2 trường hợp:
- Lấy món bên trái (món $i$): được (giá trị món $i$ × tuổi của nó) + (giá trị tối đa khi bán các món trong đoạn $[i+1, j]$), tức $v[i] \cdot t + F[i+1][j]$.
- Lấy món bên phải (món $j$): được $v[j] \cdot t + F[i][j-1]$, vì còn lại đoạn $[i, j-1]$.
Thứ tự duyệt i, j
Có công thức rồi thì vòng for(i), for(j) chạy thế nào? Cách dễ nhất là vẽ 1 bảng ra và nhìn: ô $(i, j)$ cần ô bên dưới $(i+1, j)$ và ô bên trái $(i, j-1)$. Vậy ta cần duyệt sao cho 2 ô đó đã được tính trước:
- Để ô bên dưới đã tính, $i$ phải đi từ dưới lên (
--i). - Để ô bên trái đã tính, $j$ phải đi từ trái sang phải (
++j). - $i$ không được lớn hơn $j$ (left không vượt right), và $i = j$ đã gán ở bài toán cơ sở. Nên $i$ chạy từ $n - 1$ ngược về 1, còn $j$ chạy từ $i + 1$ đến $n$.
Minh hoạ: lấp bảng F từ dưới lên
Em nhập dãy giá trị $v$ rồi bấm Tiếp để xem từng ô được tính: ô vàng là ô đang tính, 2 ô tím là ô bên dưới và ô bên trái mà nó cần. Sau khi lấp xong bảng, các bước cuối sẽ lần ngược lại xem ngày nào bán món nào để đạt đáp án:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2005;
int v[N];
ll f[N][N];
int main(){
// freopen("dprcma.inp", "r", stdin);
// freopen("dprcma.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i];
}
for(int i = 1; i <= n; ++i){
f[i][i] = v[i] * n;
}
for(int i = n - 1; i >= 1; --i){
for(int j = i + 1; j <= n; ++j){
int t = n - j + i;
f[i][j] = max(v[i] * t + f[i + 1][j], v[j] * t + f[i][j - 1]);
}
}
cout << f[1][n];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
v = [0] + [int(x) for x in data[1:n + 1]]
f = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
f[i][i] = v[i] * n
for i in range(n - 1, 0, -1):
for j in range(i + 1, n + 1):
t = n - j + i
f[i][j] = max(v[i] * t + f[i + 1][j], v[j] * t + f[i][j - 1])
print(f[1][n])Với cách trên thì ta sẽ có thể chạy nhanh hơn và ăn ít bộ nhớ hơn vì không phải tốn thời gian và bộ nhớ cho việc gọi đệ quy nữa. Độ phức tạp vẫn như cách 2:
int ($\approx 2.147 \cdot 10^9$). Mảng $f$ để long long như code trên là an toàn; còn $v[i] \cdot t \le 2 \cdot 10^6$ thì int thoải mái.Cách 4Tham khảo: rút gọn còn mảng 1 chiều
Ta hoàn toàn có thể rút gọn mảng $F$ từ 2 chiều về còn 1 chiều. Cách này là bản nâng cấp của cách bottom-up bên trên, nên để làm được nó thì ta cần nắm rõ cách 3 đó nha.
Ta rút gọn $F[i][j]$ thành $F[j]$. Lúc đầu ta để toàn bộ mảng $F = 0$ (khai báo toàn cục là có sẵn rồi), để trong quá trình chạy việc ta lấy một ô $0$ (chưa tính) cộng với $v[i] \cdot t$ hay $v[j] \cdot t$ sẽ không bị ảnh hưởng. Đáp án là $F[n]$.
Bài này hay ở chỗ vòng for(i) và for(j) gần như giữ nguyên, việc duy nhất là bỏ [i] khỏi F[i][j], và cho $i$ chạy từ $n$, $j$ chạy từ $i$ để gộp luôn bước cơ sở vào vòng lặp. Vòng for(i) ở ngoài sẽ "ngầm" đóng vai trò chỉ số [i]:
- Khi xét tới $F[j]$ (trước khi gán) thì bản chất nó đang là $F[i+1][j]$, vì $i$ chạy ngược và ô $j$ của hàng này ta chưa gán. Nên $v[i] \cdot t + F[i+1][j]$ rút gọn thành $v[i] \cdot t + F[j]$.
- Còn $F[j-1]$ thì bản chất là $F[i][j-1]$, vì $j$ chạy xuôi nên vị trí $j - 1$ vừa được cập nhật ở hàng $i$ hiện tại. Nên $v[j] \cdot t + F[i][j-1]$ rút gọn thành $v[j] \cdot t + F[j-1]$.
- Riêng ô $j = i$: $t = n$, $F[i]$ và $F[i-1]$ khi đó vẫn còn là 0 (chưa từng bị đụng tới), nên công thức cho ra đúng $v[i] \cdot n$ – chính là bài toán cơ sở.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2005;
int v[N];
ll f[N];
int main(){
// freopen("dprcma.inp", "r", stdin);
// freopen("dprcma.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i];
}
for(int i = n; i >= 1; --i){
for(int j = i; j <= n; ++j){
int t = n - j + i;
f[j] = max(v[i] * t + f[j], v[j] * t + f[j - 1]);
}
}
cout << f[n];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
v = [0] + [int(x) for x in data[1:n + 1]]
f = [0] * (n + 1)
for i in range(n, 0, -1):
for j in range(i, n + 1):
t = n - j + i
f[j] = max(v[i] * t + f[j], v[j] * t + f[j - 1])
print(f[n])Với cách trên ta chỉ dùng mảng 1 chiều nên tốn ít bộ nhớ hơn hẳn, tốc độ truy xuất phần tử trên mảng 1 chiều cũng nhanh hơn nên code chạy nhanh hơn nữa.
Tuy vậy để làm ra được cách này thì các bạn phải làm được cách bottom-up trước. Nên trong đi thi thì anh em làm cách nào anh em thấy dễ và làm nhanh để có thể AC được là ok rồi.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét