Trò Chơi Nhặt Tiền
Đề bài
Hai người chơi một trò chơi với những đồng xu, luật chơi như sau:
- Ban đầu họ có $N$ đồng xu đánh số $1, 2, \ldots, N$, đồng xu thứ $i$ có giá trị $c_i$.
- Hai người luân phiên thực hiện lượt đi, họ nhặt các đồng xu theo thứ tự $1, 2, \ldots, N$.
- Người đi lượt đầu tiên nhặt lấy 1 hoặc 2 đồng xu đầu tiên.
- Người đi sau phải nhặt các đồng xu kế tiếp, số lượng ít nhất là 1, nhiều nhất gấp đôi số đồng xu người kia vừa nhặt.
- Trò chơi kết thúc khi tất cả các đồng xu đều đã bị nhặt hết.
- Mục tiêu của mỗi người chơi là tổng giá trị các đồng xu người đó nhặt được là lớn nhất.
Giả sử hai người đều chơi tối ưu, xác định tổng giá trị lớn nhất người đi trước có thể đạt được.
Dữ liệu:
- Dòng 1: số nguyên $N$ $(5 \le N \le 2000)$.
- Dòng $2 \ldots N + 1$: $N$ số nguyên $c_1, c_2, \ldots, c_N$ $(1 \le c_i \le 10^5)$.
Kết quả:
- Dòng 1: số nguyên kết quả.
Subtask:
- 40% số test đầu tiên có $N \le 200$.
- 60% số test còn lại không có giới hạn gì thêm.
5
1
3
1
7
29Lờ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 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
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 CodeforcesĐây là một bài trò chơi đối kháng kinh điển: cả hai người đều chơi tối ưu, nên ta không thể "tham lam" kiểu lượt nào cũng nhặt nhiều nhất có thể được, mà phải tính trước xem mỗi lựa chọn sẽ dẫn tới kết cục thế nào. Công cụ cho việc này chính là quy hoạch động.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Ví dụGiải thích ví dụ 1 3 1 7 2
Dãy đồng xu là $1, 3, 1, 7, 2$. Người chơi 1 đi trước, được nhặt 1 hoặc 2 đồng xu đầu tiên:
Trường hợp 1 – người chơi 1 lượm 2 đồng xu đầu tiên $(1, 3)$: người chơi 1 hiện tại sẽ có tổng giá trị các đồng xu là 4. Người chơi thứ 2 sau đó được quyền lựa chọn trong phạm vi 4 đồng xu ⇒ người thứ 2 sẽ lượm hết để tối ưu tổng giá trị ⇒ người thứ hai có tổng giá trị các đồng xu là $1 + 7 + 2 = 10$. Người chơi 1 chỉ được 4.
Trường hợp 2 – người chơi 1 lượm 1 đồng xu đầu tiên $(1)$: người chơi 1 hiện tại có tổng giá trị là 1. Người chơi 2 có quyền lựa chọn trong phạm vi 2 đồng xu:
- Nếu người chơi 2 lựa chọn 2 đồng xu $(3, 1)$, thì tổng giá trị của người chơi thứ 2 sẽ là 4 và người chơi 1 lại có thể lựa chọn trong phạm vi 4 đồng xu ⇒ người chơi 1 sẽ lấy hết các đồng xu còn lại ⇒ người chơi 1 có tổng giá trị là $1 + 7 + 2 = 10$.
- Nếu người chơi 2 lựa chọn 1 đồng xu $(3)$, tổng giá trị người thứ 2 hiện tại là 3 và người chơi 1 sau đó có quyền chọn trong phạm vi 2 đồng xu. Dễ thấy người chơi 1 nên lấy hết cả 2 đồng xu tiếp theo $(1, 7)$. Tổng giá trị hiện tại của người chơi 1 sẽ là $1 + 1 + 7 = 9$, và người chơi thứ 2 sẽ lượm đồng xu cuối cùng.
Từ hai nhánh trên, vì đang là lượt chơi của người chơi thứ 2 nên họ sẽ cố gắng tối ưu tổng giá trị đồng xu của họ nhất có thể, tương đương với việc làm tối thiểu số giá trị của người thứ 1 nhất có thể. Do đó người chơi thứ 2 sẽ chọn cách lấy 1 đồng xu, và kết quả sau cùng trường hợp này là người chơi 1 có tối đa 9.
Trong hai cách lựa chọn lượt đi đầu của người chơi 1 ở trên, ta thấy cách thứ 2 là đem lại tổng giá trị lớn nhất nếu cả hai cùng chơi tối ưu (9 so với 4), do đó kết quả là 9.
Ý tưởngTrạng thái f[i][j][k] và hiệu số
Ta gọi f[i][j][k] với:
- $i$ có nghĩa là còn $n - i + 1$ đồng xu (tính cả đồng xu vị trí $i$) chưa được nhặt, tức là các đồng $i, i + 1, \ldots, n$.
- $j$ có nghĩa là số lượng đồng xu người chơi hiện tại được phép bốc (tối đa).
- $k$ có nghĩa là người chơi hiện tại là người đi trước ban đầu hay người đi sau ($k = 0$ là người chơi đi trước – người thứ nhất, $k = 1$ là người chơi đi sau – người thứ hai).
Giá trị f[i][j][k] là hiệu giữa tổng giá trị các đồng xu mà người thứ nhất nhặt được với tổng giá trị các đồng xu mà người thứ hai nhặt được (tính trên phần còn lại $i..n$), khi cả hai chơi tối ưu. Xét các trường hợp sau:
- Nếu $k = 0$: người chơi thứ nhất sẽ cố gắng tối ưu hiệu này, đồng nghĩa với việc người chơi thứ nhất sẽ xem xét chọn lựa nước đi sao cho hiệu của những lượt đi sau thu được phải là lớn nhất có thể. Do đó ta có công thức truy hồi: $$f[i][j][0] = \max_{1 \le u \le j}\Big(f[i + u][\min(2u, n)][1] + sum[i][i + u - 1]\Big)$$
- Nếu $k = 1$: tương tự nhưng thay vì lấy tối đa là lấy tối thiểu (người thứ hai muốn hiệu càng nhỏ càng tốt), và lượt sau dành cho người thứ nhất: $$f[i][j][1] = \min_{1 \le u \le j}\Big(f[i + u][\min(2u, n)][0] - sum[i][i + u - 1]\Big)$$
Với:
- $sum[i][i + u - 1]$: tổng đoạn con từ $i$ đến $i + u - 1$. Có thể tính sẵn mảng
sumnày với mảng cộng dồn cơ bản. - $f[i + u][\min(2u, n)][1]$ có nghĩa là nếu ta chọn nhặt $u$ đồng xu tiếp theo thì sẽ đến lượt người chơi thứ hai đi với giới hạn lựa chọn là $\min(2u, n)$ (người chơi thứ hai không thể bốc quá số lượng đồng xu ban đầu).
- Nếu $i + u = n + 1$ tức là nhặt $u$ đồng là hết sạch xu, trò chơi kết thúc: hiệu chính là $+sum[i][n]$ (người thứ nhất nhặt) hoặc $-sum[i][n]$ (người thứ hai nhặt).
được + sum[i][i+u−1]
return trong code.Vì sao lại lưu hiệu mà không lưu thẳng tổng của từng người? Vì với hiệu thì cả 2 người cùng "kéo co" trên 1 con số: người thứ nhất kéo lên (max), người thứ hai kéo xuống (min). Một con số duy nhất là đủ mô tả kết cục của mỗi trạng thái.
Thứ tự tính: f[i][..][..] cần f[i + u][..][..] với $u \ge 1$ nên ta cho $i$ chạy từ $n$ về $1$.
Em nhập dãy đồng xu rồi bấm Tiếp để xem hai người chơi tối ưu: ở mỗi lượt, người chơi tra bảng f để biết mỗi lựa chọn $u$ dẫn tới hiệu $A - B$ cuối cùng bằng bao nhiêu, rồi chọn cái tốt nhất cho mình:
Subtask 1Duyệt mọi lựa chọn u – O(N³)
Đến đây, ta có hai cách xử lý. Cách trâu: với mỗi trạng thái f[i][j][k] ta duyệt qua tất cả những lựa chọn $u$ (trong code là biến k của vòng lặp trong cùng) có thể xảy ra. Có $O(N^2)$ trạng thái, mỗi trạng thái duyệt $O(N)$ lựa chọn ⇒ $O(N^3)$, chỉ đủ cho subtask 1 ($N \le 200$).
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[2005];
int f[2005][2005][2], sum[2005][2005];
int solve()
{
for (int i = 1; i <= n; i ++)
{
sum[i][i] = a[i];
for (int j = i + 1; j <= n; j ++)
{
sum[i][j] = sum[i][j - 1] + a[j];
}
}
for (int i = n; i >= 1; i --)
{
for (int j = 1; j <= n; j ++)
{
// f[i][j][k] neu gioi han la j
// Player 1
f[i][j][0] = -1e18;
for (int k = 1; k <= j; k ++)
{
if (i + k == (n + 1))
{
f[i][j][0] = max(f[i][j][0], sum[i][n]);
}
else f[i][j][0] = max(f[i + k][min(n, k * 2)][1] + sum[i][i + k - 1], f[i][j][0]);
}
// Player 2
f[i][j][1] = 1e18;
for (int k = 1; k <= j; k ++)
{
if (i + k == (n + 1)) f[i][j][1] = min(f[i][j][1], -sum[i][n]);
else f[i][j][1] = min(f[i + k][min(n, k * 2)][0] - sum[i][i + k - 1], f[i][j][1]);
}
}
}
return (f[1][2][0] + sum[1][n]) / 2;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
cout << solve() << endl;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(x) for x in data[1:n + 1]]
# pre[i] = a[1] + ... + a[i] -> sum[i][j] = pre[j] - pre[i - 1]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i]
INF = 10 ** 18
# f0[i][j]: lượt người thứ nhất, f1[i][j]: lượt người thứ hai
f0 = [[0] * (n + 1) for _ in range(n + 2)]
f1 = [[0] * (n + 1) for _ in range(n + 2)]
for i in range(n, 0, -1):
for j in range(1, n + 1):
best0, best1 = -INF, INF
for k in range(1, j + 1):
s = pre[min(i + k - 1, n)] - pre[i - 1]
if i + k >= n + 1:
s = pre[n] - pre[i - 1]
best0 = max(best0, s)
best1 = min(best1, -s)
break # k lớn hơn nữa cũng là lấy hết
nk = min(n, k * 2)
best0 = max(best0, f1[i + k][nk] + s)
best1 = min(best1, f0[i + k][nk] - s)
f0[i][j] = best0
f1[i][j] = best1
print((f0[1][2] + pre[n]) // 2)
main()Lưu ý nhỏ: khi $i + k > n + 1$ (nhặt nhiều hơn số xu còn lại) thì code vẫn nhảy vào nhánh else, nhưng các phần tử mảng toàn cục ngoài phạm vi đều bằng 0 nên giá trị thu được là 0, không bao giờ tốt hơn lựa chọn "nhặt hết" (vì $c_i \ge 1$), nên kết quả vẫn đúng.
Subtask 2Tận dụng f[i][j − 1] – O(N²)
Thay vì cứ mỗi lần ta duyệt qua những lựa chọn $u$, ta có thể thấy nếu đang cần tính f[i][j][0] thì ta đã tính được f[i][j - 1][0]. Sự khác biệt giữa f[i][j][0] và f[i][j - 1][0] chỉ khác ở chỗ là f[i][j][0] có thêm đúng một lựa chọn là $u = j$. Khi đấy, ta có thể tối ưu công thức truy hồi như sau:
Còn nếu $i + j > n$ thì được phép nhặt hết toàn bộ các đồng xu còn lại, và vì các đồng xu đều có giá trị dương nên nhặt hết luôn là tốt nhất: f[i][j][0] = sum[i][n], f[i][j][1] = -sum[i][n]. Mỗi trạng thái giờ chỉ mất $O(1)$ ⇒ tổng $O(N^2)$.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[2005];
int f[2005][2005][2], sum[2005][2005], mx[2005], mn[2005];
int solve()
{
for (int i = 1; i <= n; i ++)
{
sum[i][i] = a[i];
for (int j = i + 1; j <= n; j ++)
{
sum[i][j] = sum[i][j - 1] + a[j];
}
}
for (int i = n; i >= 1; i --)
{
for (int j = 1; j <= n; j ++)
{
f[i][j][0] = - 1e18;
f[i][j][1] = 1e18;
if (j != 1)
{
f[i][j][0] = f[i][j - 1][0];
f[i][j][1] = f[i][j - 1][1];
}
if ((i + j) > n)
{
f[i][j][0] = sum[i][n];
f[i][j][1] = -sum[i][n];
}
else
{
f[i][j][0] = max(f[i][j][0], f[i + j][min(n, j * 2)][1] + sum[i][i + j - 1]);
f[i][j][1] = min(f[i][j][1], f[i + j][min(n, j * 2)][0] - sum[i][i + j - 1]);
}
}
}
return (f[1][2][0] + sum[1][n]) / 2;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
cout << solve() << endl;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(x) for x in data[1:n + 1]]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i]
INF = 10 ** 18
f0 = [[0] * (n + 1) for _ in range(n + 2)]
f1 = [[0] * (n + 1) for _ in range(n + 2)]
for i in range(n, 0, -1):
r0, r1 = f0[i], f1[i]
cur0, cur1 = -INF, INF # f[i][j - 1][0], f[i][j - 1][1]
rest = pre[n] - pre[i - 1] # sum[i][n]
for j in range(1, n + 1):
if i + j > n:
cur0, cur1 = rest, -rest # lấy hết các đồng xu còn lại
else:
s = pre[i + j - 1] - pre[i - 1]
nj = min(n, j * 2)
v0 = f1[i + j][nj] + s
v1 = f0[i + j][nj] - s
if v0 > cur0: cur0 = v0
if v1 < cur1: cur1 = v1
r0[j] = cur0
r1[j] = cur1
print((f0[1][2] + pre[n]) // 2)
main()Với $N = 2000$ thì có $2000 \times 2000 \times 2 = 8 \cdot 10^6$ trạng thái, mỗi trạng thái $O(1)$, chạy rất nhanh. Bộ nhớ: mảng f và sum kiểu long long khoảng $96$ MB; bản Python (mình viết thêm) dùng mảng cộng dồn 1 chiều thay cho sum[i][j] nên nhẹ hơn.