Chia Trang
Đề bài
Văn bản là một dãy gồm $N$ từ đánh số từ 1 đến $N$. Từ thứ $i$ có độ dài là $w_i$. Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài tối đa là $L$: sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá $L$.
Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số $\mathbf{L - S}$, trong đó $\mathbf{S}$ là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.
Bạn hãy lập chương trình nhận đầu vào là danh sách các từ, tìm cách phân trang với hệ số phạt nhỏ nhất.
Dữ liệu nhập:
- Dòng 1 chứa 2 số nguyên dương $N, L$ $(1 \le N \le 6000,\ 1 \le L \le 1000)$.
- Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa số nguyên dương $w_i$ $(1 \le w_i \le L)$.
Kết quả: in ra hệ số phạt nhỏ nhất.
Subtask:
- 20% số test đầu tiên có $N \le 20$.
- 30% số test tiếp theo có $N, L \le 100$.
- 20% số test tiếp theo có $N, L \le 1000$.
- 30% số test còn lại không có giới hạn gì thêm.
4 5
3
2
2
42Giải thích: trong ví dụ trên ta có thể phân thành 3 dòng:
- Dòng 1: gồm một từ (3), hệ số phạt dòng này là $5 - 3 = 2$.
- Dòng 2: gồm hai từ (2, 2), hệ số phạt là $5 - 4 = 1$.
- Dòng 3: gồm một từ (4), hệ số phạt là $5 - 4 = 1$.
- Đáp án: $\max(2, 1, 1) = 2$.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Đề bàiTóm tắt lại cho dễ hiểu
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:
Cho số nguyên dương $n$ $(1 \le n \le 6000)$ là số từ trong văn bản; phân trang là 1 cách sắp xếp lần lượt $n$ từ của văn bản vào dãy các dòng; mỗi dòng có độ dài tối đa là $L$ $(1 \le L \le 1000)$, tức tổng độ dài các từ trên cùng một dòng không được $> L$. Từ thứ $i$ $(1 \le i \le n)$ trong văn bản có độ dài là $w[i]$ $(1 \le w[i] \le L)$.
Biết hệ số phạt của mỗi dòng là $L - S$ với $S$ là tổng độ dài của các từ trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong các hệ số phạt của các dòng. Hãy tìm cách phân trang (sắp xếp các từ liên tiếp vào dãy các dòng) với hệ số phạt của cách phân trang là nhỏ nhất; in ra hệ số phạt đó.
Ví dụ: $n = 4$; $L = 5$; $w = \{3, 2, 2, 4\}$. Ta sẽ chia thành 3 dòng là (3); (2, 2); (4). Hệ số phạt của các dòng lần lượt là $(5 - 3); (5 - 4); (5 - 4)$ $= (2); (1); (1)$. Từ đó hệ số phạt của cách phân trang là $\max(2, 1, 1) = 2$. Vậy đáp án $= 2$.
Ví dụ: $n = 4$; $L = 10$; $w = \{1, 5, 5, 6\}$. Thì ta sẽ chia là 3 dòng là (1, 5); (5); (6). Hệ số phạt của cách phân trang là $5$.
Chứ ta không được chia thành 2 dòng là (1, 6); (5, 5) được đâu nha. Vì (1, 6) là từ thứ nhất và từ thứ 4; 2 từ đó không liên tiếp nhau nên ta không sắp xếp thế được.
Mình sẽ gọi tắt hệ số phạt của cách phân trang là hệ số phạt trang; còn hệ số phạt của dòng thì mình gọi là hệ số phạt dòng.
Cách 1Vét cạn bằng đệ quy – thử mọi cách chia
Cách làm đơn giản nhất của bài này chính là vét cạn; tức là ta thử mọi trường hợp có thể đó. Tuy vậy nhưng để thực hiện cách này thì khá là phức tạp nên các bạn tham khảo thôi nha.
Ý tưởng
Vì các từ trong 1 dòng phải liên tiếp nhau nên ta sẽ có ý tưởng như sau. Ví dụ ta đang xét phần tử thứ $n$; thì lúc đầu ta chỉ nhét vào dòng ta đang xét phần tử thứ $n$ thôi; lúc này dòng đó có $S = w[n]$ ($S$ là tổng độ dài của dòng). Hệ số phạt trang nhỏ nhất có thể với trang đó có chứa dòng ta đang xét sẽ chính $=$ max(hệ số phạt dòng ta đang xét, hệ số phạt trang nhỏ nhất có thể với trang chứa $n - 1$ phần tử còn lại). Rồi ta sẽ dùng cái hệ số phạt trang đó để cập nhật biến kết quả.
Tiếp tới ta nhét thêm từ thứ $n - 1$ vào dòng ta đang xét; lúc này $S \mathrel{+}= w[n - 1]$. Nếu $S \le L$ tức là dòng ta đang xét có thể chứa 2 từ là từ thứ $n$ và $n - 1$. Vậy hệ số phạt trang nhỏ nhất có thể với trang có chứa dòng ta đang xét sẽ chính $=$ max(hệ số phạt dòng ta đang xét, hệ số phạt trang nhỏ nhất có thể với trang chứa $n - 2$ phần tử còn lại). Từ đó ta lại cập nhật kết quả; ta sẽ cứ lần lượt thêm các từ vào dòng ta xét cho đến khi $S > L$.
Khi $S > L$ thì từ ta đang xét không thể thêm vào dòng ta đang xét được nữa; vì nếu thêm vào thì ta sẽ vượt qua giới hạn độ dài của dòng. Lúc này ta đã thử xong mọi trường hợp có thể rồi; vì ta không thể thêm tiếp 1 từ liên tiếp nào nữa vào dòng ta đang xét nữa. Nên ta sẽ trả về biến kết quả thôi.
Cây đệ quy của Try(4, 5) với $w = \{3, 2, 2, 4\}$. Số trên cạnh là hệ số phạt của dòng vừa tạo. Ô vàng là các lời gọi bị lặp lại (ví dụ Try(1, 5) bị gọi 2 lần) – đây chính là chỗ Cách 2 sẽ tối ưu.
Giờ mình sẽ đi vào các bước cụ thể. Mình sẽ thực hiện như sau:
Try(n, L) sẽ trả về hệ số phạt trang nhỏ nhất có thể (với trang đó chứa $n$ từ đầu tiên và mặc định ở đây mỗi dòng sẽ đều có độ dài tối đa là $L$).Điều kiện dừng
Ta sẽ nhận ra là nếu trang không có từ nào cả, tức $n = 0$ thì hệ số phạt trang sẽ $= 0$. Vì ta không có từ nào cả dẫn đến không có dòng nào cả; từ đó hệ số phạt trang $=$ hệ số phạt dòng $= 0$.
Nhiều bạn sẽ nghĩ nếu không có từ nào cả thì cái dòng đó sẽ không có kí tự nào cả; dẫn đến độ dài của dòng $= 0$; từ đó hệ số phạt của dòng đó là $L - 0 = L$. Nếu ta nghĩ theo kiểu đó thì ngay từ ví dụ bài cho; ta đâu phân chia thành 3 dòng đâu; mà ta đang chia thành 4 dòng với dòng thứ 4 là dòng không có kí tự nào cả; dòng đó sẽ có hệ số phạt là $L$ thì dẫn đến hệ số phạt trang là $= \max(2, 1, 1, L) = L = 5$ đó chứ.
Chính vì vậy nên ta sẽ kết luận rằng khi $n = 0$, tức là trang không có từ nào, dẫn đến không có dòng nào thì hệ số phạt dòng $= 0$; từ đó hệ số phạt trang cũng sẽ $= 0$. Vậy điều kiện dừng sẽ là if(n == 0) {return 0;}
Xử lý chạy
Ở đây thì mình lấy ví dụ cho các bạn dễ hình dung nha. $n = 4$; $L = 5$; $w = \{3, 2, 2, 4\}$. Ta cần hệ số phạt trang nhỏ nhất khi xét $n$ phần tử đầu nên sẽ gọi hàm Try(4, L).
- Ta sẽ gọi biến
reschính là kết quả củaTry(4, L). Vì ta cần hệ số phạt trang nhỏ nhất nên lúc đầu ta khởi tạores = L; tức là khởi tạo bằng thứ to nhất có thể để tiện cập nhật trong quá trình tính. - Gọi biến
Schính là độ dài của dòng ta đang xét; lúc đầu dòng ta xét chưa có gì cả nênS = 0. - Ta sẽ lần lượt thêm vào dòng ta xét từ thứ $n$; sau đó thêm từ thứ $n - 1$; cứ như vậy đến từ thứ 1. Vậy ta sẽ dùng 1 vòng
for(int i = n; i >= 1; --i). Vậy ở mỗi lần ta đang thêm vào dòng ta đang xét từ thứ $i$. - Khi thêm từ thứ $i$ vào dòng ta đang xét thì
S += w[i]; tức tổng độ dài của dòng sẽ được tăng thêm $w[i]$. Lúc này thìS += w[4]và $S = 4$. - Sau bước trên ta kiểm tra dòng ta đang xét có tổng độ dài là $S$ có thoả mãn là độ dài của nó $\le L$ không, tức có thoả mãn $S \le L$ không. Nếu có thì chứng tỏ dòng ta đang xét là hợp lệ; vậy giờ ta đi cập nhật kết quả của biến
res. ($S \le L$) ở đây là ($4 \le 5$); thoả mãn nên ta tới bước tiếp.- Hệ số phạt trang nhỏ nhất với trang có $n$ phần tử đầu (
res) $=$ min(res, hệ số phạt trang nhỏ nhất với trang có dòng ta đang xét và tổng cộng có $n$ phần tử đầu). - Hệ số phạt trang nhỏ nhất với trang có dòng ta đang xét và tổng cộng có $n$ phần tử đầu $=$ max(hệ số phạt dòng ta đang xét, hệ số phạt trang nhỏ nhất với trang có $i - 1$ phần tử đầu) (vì dòng ta đang xét có chứa phần tử thứ $i$ tới phần tử thứ $n$ rồi nên chỉ còn $i - 1$ phần tử còn lại thôi) $=$
max(L - S, Try(i - 1, L)).
- Hệ số phạt trang nhỏ nhất với trang có $n$ phần tử đầu (
Lúc này ta sẽ cập nhật res = min(res, max(L - S, Try(i - 1, L))) $=$ min(5, max(5 - 4, Try(3, 5))). Ở đây $5 - 4$ chính là hệ số phạt của dòng ta đang xét; Try(3, 5) chính là hệ số phạt trang nhỏ nhất với trang chứa 3 phần tử đầu. max(5 - 4, Try(3, 5)) chính là hệ số phạt trang nhỏ nhất với trang có chứa dòng ta đang xét (là dòng có mỗi từ thứ 4 đó) và trang có chứa 4 phần tử đầu. Từ đó ta cần kết quả đó để cập nhật với biến res; vì biến res sẽ lưu hệ số phạt trang nhỏ nhất có thể với trang chứa 4 phần tử đầu; nên res = min(res, max(5 - 4, Try(3, 5))) = min(L, max(5 - 4, Try(3, 5))). Vì lúc đầu ta gán res = L.
- Nếu $S > L$ thì ta sẽ
break; vì không thể thêm từ ta đang xét vào dòng ta đang xét được (thêm vào thì nó vượt qua giới hạn mà). Vậy ta không thể thêm từ đang xét vào dòng ta đang xét nữa thì phảibreakthôi; ta không thể qua từ tiếp theo được nữa vì nếu qua thì từ đó sẽ không liên tiếp với các từ trong dòng.
Sau các bước trên thì ta thêm phần tử $i = n - 1$ vào dòng ta đang xét nữa thì $S = 4 + 2 = 6$. Lúc này $S > L$ nên ta break. Vậy res = min(L, max(5 - 4, Try(3, 5))) chính là kết quả của bài toán luôn. Try(3, 5) hay chính là Try(i - 1, L) chính là bước gọi đệ quy ở phần xử lý chạy đó anh em.
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = 6005;
int w[nMax];
int Try(int n, int L){
if(n == 0){
return 0;
}
int res = L, S = 0;
for(int i = n; i >= 1; --i){
S += w[i];
if(S <= L){
res = min(res, max(L - S, Try(i - 1, L)));
}
else{
break;
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, L;
cin >> n >> L;
for(int i = 1; i <= n; ++i){
cin >> w[i];
}
cout << Try(n, L);
return 0;
}import sys
def Try(n, L, w):
# hệ số phạt trang nhỏ nhất khi xếp n từ đầu tiên
if n == 0:
return 0
res, S = L, 0
for i in range(n, 0, -1):
S += w[i]
if S <= L:
res = min(res, max(L - S, Try(i - 1, L, w)))
else:
break
return res
def main():
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
w = [0] + [int(x) for x in data[2:2 + n]]
print(Try(n, L, w))
main()Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 2 dòng này. Trong bài này thì đầu vào tối đa chỉ tầm 6000 số thì các bạn không cần thêm cũng được nhưng mình vẫn thêm vì đó là thói quen nha. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.const int nMax = 6005;ở đây chính là $n$ tối đa $= 6000$. Và mình vẫn $+$ thêm 5 vào cho chắc nha.
Cách này thử mọi cách chia nên số lời gọi đệ quy có thể lên tới cỡ $2^{n-1}$ (ví dụ khi mọi từ đều dài 1 và $L$ lớn). Vì vậy nó chỉ ăn được subtask $N \le 20$ thôi nha.
Biến thể: chọn từ đầu dãy thay vì từ cuối dãy
Nếu các bạn không thích xét theo kiểu chọn phần tử thứ $n$ rồi $n - 1$ mà muốn chọn kiểu dòng mình đang xét sẽ chọn phần tử thứ 1 rồi chọn thêm phần tử thứ 2 rồi cứ vậy thì mình sẽ sửa một chút code ở trên nha.
- Lúc này hàm
Try(i)sẽ trả về hệ số phạt trang nhỏ nhất với trang chứa các phần tử từ $i$ tới $n$. - Vậy lúc này nếu $i == n + 1$, tức là ta không còn từ nào để xét thì ta sẽ
returnvề 0; vì ta sẽ không tạo được dòng nào cả. - Ta sẽ làm vòng
for($j = i$; $j$ chạy đến $n$); thêm phần tử $a[j]$ vào dòng ta đang xét và cập nhật biếnresthôi. Lúc này ta phải gọi đệ quy làTry(j + 1); vì lúc này dòng ta đang xét sẽ lấy các phần tử từ thứ $i$ tới $j$; thì còn lại chính là ta phải phân trang với trang chứa từ phần tử thứ $j + 1$ tới $n$ rồi.
Sau đây là Source Code cho cách vét cạn mà ta sẽ đi từ việc chọn phần tử thứ 1 lên thay vì chọn phần tử thứ $n$:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = 6005;
int n, L;
int a[nMax];
int Try(int i)
{
if(i == n + 1) return 0;
int res = L, sum = 0;
for(int j = i; j <= n; ++j)
{
sum += a[j];
if(sum <= L) res = min(res, max(L - sum, Try(j + 1)));
else break;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> L;
for(int i = 1; i <= n; ++i) cin >> a[i];
cout << Try(1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
def Try(i):
# hệ số phạt trang nhỏ nhất khi xếp các từ i..n
if i == n + 1:
return 0
res, s = L, 0
for j in range(i, n + 1):
s += a[j]
if s <= L:
res = min(res, max(L - s, Try(j + 1)))
else:
break
return res
print(Try(1))
main()Cách 2Đệ quy có nhớ (quy hoạch động top-down) – O(N·L)
Và nếu anh em code được cách vét cạn thì ở hàm Try(n, L) ta thấy chỉ có biến $n$ thay đổi thôi. Ví dụ trong cây đệ quy ở trên, Try(2, 5), Try(1, 5), Try(0, 5) bị gọi đi gọi lại nhiều lần mà lần nào cũng ra đúng một kết quả.
Vậy để tránh trường hợp lặp thì ta sẽ tạo một mảng F[nMax] để có biến F[n] sẽ lưu trữ kết quả của hàm Try(n, L). Lúc đầu ta sẽ khởi tạo toàn bộ mảng F là $= -1$ nha; có nghĩa là nếu F[n] != -1 thì Try(n, L) ta đã tính rồi và đã lưu kết quả vào F[n]. Đó chính là phương pháp quy hoạch động top-down – đệ quy có nhớ.
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = 6005;
int w[nMax], f[nMax];
int Try(int n, int L){
if(n == 0){
return 0;
}
if(f[n] != -1){
return f[n];
}
int res = L, S = 0;
for(int i = n; i >= 1; --i){
S += w[i];
if(S <= L){
res = min(res, max(L - S, Try(i - 1, L)));
}
else{
break;
}
}
return f[n] = res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
fill(&f[1], &f[nMax], -1);
int n, L;
cin >> n >> L;
for(int i = 1; i <= n; ++i){
cin >> w[i];
}
cout << Try(n, L);
return 0;
}import sys
import threading
def main():
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
w = [0] + [int(x) for x in data[2:2 + n]]
f = [-1] * (n + 1)
f[0] = 0 # Try(0) = 0
def Try(n):
if f[n] != -1: # đã tính rồi thì lấy ra dùng luôn
return f[n]
res, S = L, 0
for i in range(n, 0, -1):
S += w[i]
if S <= L:
res = min(res, max(L - S, Try(i - 1)))
else:
break
f[n] = res
return res
print(Try(n))
# đệ quy sâu tới 6000 tầng nên tăng giới hạn đệ quy và kích thước stack
sys.setrecursionlimit(20000)
threading.stack_size(256 * 1024 * 1024)
t = threading.Thread(target=main)
t.start()
t.join()Giải thích một số chỗ trong code
fill(&f[1], &f[nMax], -1);đây chính là ta lấp đầy mảngfbằng $-1$. Tại sao ta lại lấp từ phần tử số 1 mà không phải từ phần tử số 0? Vìf[0] = Try(0, L) = 0; mảngfta khai báo toàn cục nênf[0] = 0sẵn rồi nên ta lấp đầy mảng từ phần tử 1 thôi.return f[n] = res;đây chính là gánf[n] = resrồireturn f[n]nha.
Đánh giá độ phức tạp
- Độ phức tạp không gian (Space Complexity): $O(2 \cdot n)$; vì ta đang dùng hai mảng
wvàf. - Độ phức tạp thời gian (Time Complexity): $O(n \cdot L)$. Vì trong trường hợp tệ nhất ta sẽ phải lấp đầy mảng
f; trong quá trình lấp đầy mảngfthì với mỗi phần tử, tức $n$, thì vòngfor($i$ bên trong) sẽ chạy tối đa là $L$ chứ không phải là $n$. Mặc dù về lý thuyết là chạy từ $n$ về tới 1; nhưng không phải vậy vì $w[i] \ge 1$; nên nếu có bằng hết 1 thì sau mỗi bước $S$ của ta sẽ tăng lên 1; thành ra tối đa $L + 1$ bước là ta đã có $S > L$ vàbreakvòng lặp rồi. Từ đó độ phức tạp thời gian của ta là $O(n \cdot L)$ chứ KHÔNG phải $O(n^2)$.
Cách 3Quy hoạch động bottom-up – công thức truy hồi
Cách tiếp cận đệ quy trên thì sẽ khá là khó hiểu. Vậy giờ ta sẽ đến với cách dùng quy hoạch động bottom-up (chính là tạo công thức truy hồi đó anh em), có khi sẽ dễ hiểu hơn nha. Cho anh em 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]$ là hệ số phạt trang nhỏ nhất khi xét $i$ phần tử ($i$ từ) đầu tiên $(0 \le i \le n)$.
Bước 2: Xác định bài toán cơ sở
Khi ta không xét phần tử nào, tức là ta không có từ nào, dẫn đến ta không có dòng nào, dẫn đến ta không có trang nào. Từ đó hệ số phạt trang sẽ chỉ có thể $= 0$. Vậy $F[0] = 0$.
Ta cũng sẽ khởi tạo tất cả các phần tử còn lại trong mảng $F$ bằng $L$, tức bằng giá trị phạt lớn nhất để có thể tiện cập nhật. Vậy ta sẽ fill(&F[1], &F[n + 1], L).
Bước 3: Xác định đáp án của bài toán
Ta cần tìm hệ số phạt trang nhỏ nhất khi xét $n$ phần tử ($n$ từ) đầu tiên nên hiển nhiên kết quả của bài toán sẽ là $F[n]$.
Bước 4: Xác định công thức truy hồi
Khi xét đến phần tử thứ $i$ ta đang có dãy đang xét là $1, 2, \ldots, i - 1, i$.
- Ta lấy phần tử thứ $i$ vào riêng một dòng; vậy phần còn lại chính là $1, 2, \ldots, i - 1$.
- Tổng quát nếu ta lấy phần tử thứ $i$ đến phần tử thứ $j$ (với $j \le i$; ở đây ta đang lấy ngược từ $i$ về $j$) vào riêng một dòng thì phần còn lại sẽ là $1, 2, \ldots, j - 1$.
Ở trường hợp này (ta đang lấy dòng có các phần tử từ $i$ tới $j$ và phần còn lại) hệ số phạt trang nhỏ nhất có thể có của ta sẽ là max(hệ số phạt dòng chứa phần tử $i$ đến phần tử thứ $j$, hệ số phạt trang nhỏ nhất có thể có với trang chứa $1, 2, \ldots, j - 1$), và chính $= \max(L - S, F[j - 1])$ với $S$ chính là độ dài của dòng ta có; ở đây $S = w[i] + w[i - 1] + \ldots + w[j]$.
Nếu $S \le L$ thì ta cập nhật $F[i] = \min(F[i], \max(L - S, F[j - 1]))$. Vì trường hợp mà ta lấy lần lượt phần tử $i$ ra 1 dòng và phần còn lại; phần tử ($i$ và $i - 1$) ra 1 dòng và phần còn lại; …; phần tử ($i, i - 1, \ldots, j$) ra 1 dòng và phần còn lại. Tất cả các trường hợp đó đều sẽ có thể xảy ra và ta cần tìm trường hợp có hệ số phạt trang nhỏ nhất; đó là lý do $F[i] = \min(F[i], \ldots)$, ở đây $\ldots$ chính là hệ số phạt trang nhỏ nhất ở trường hợp đó; nó chính là $\max(L - S, F[j - 1])$.
Vậy ta có công thức truy hồi là:
Với $S$ lần lượt bằng $w[i]$; $w[i] + w[i - 1]$; $w[i] + w[i - 1] + w[i - 2]$; …; $w[i] + w[i - 1]$ $+ w[i - 2] + \ldots$ $+ w[j]$ $(1 \le j \le i)$.
Em nhập $L$ và dãy độ dài các từ rồi bấm Tiếp để xem bảng $F$ được lấp đầy từng ô; cuối cùng mình truy vết lại cách chia trang tốt nhất cho em xem luôn:
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = 6005;
int w[nMax], f[nMax];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, L;
cin >> n >> L;
f[0] = 0;
fill(&f[1], &f[n + 1], L);
for(int i = 1; i <= n; ++i){
cin >> w[i];
int S = 0;
for(int j = i; j >= 1; --j){
S += w[j];
if(S <= L){
f[i] = min(f[i], max(L - S, f[j - 1]));
}
else{
break;
}
}
}
cout << f[n];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
w = [0] + [int(x) for x in data[2:2 + n]]
f = [L] * (n + 1)
f[0] = 0
for i in range(1, n + 1):
S = 0
best = L
for j in range(i, 0, -1):
S += w[j]
if S > L:
break
# max(L - S, f[j - 1])
cand = L - S if L - S > f[j - 1] else f[j - 1]
if cand < best:
best = cand
f[i] = best
print(f[n])
main()Đánh giá độ phức tạp
Độ phức tạp của không gian và thời gian của ta sẽ giống với cách quy hoạch động top-down thôi. Nhưng vì ta không phải gọi đệ quy nên cách này sẽ tốn ít thời gian và bộ nhớ hơn nha.
Nhận xét
Đăng nhận xét