---
tags: VNOJ, THT, Backtrack, Brute-forces, Meet In The Middle, DP, DP-knapsack, DP-Space Optimized, duyle, kazamahoang, SPyofgame
title: 🌱 Tin học trẻ 2021 - Vòng khu vực - Bảng B - Kho báu
author: Editorial-Slayers Team
license: Public domain
---
<style>
.markdown-body { max-width: 2048px; }
</style>
$\Huge \text{🌱 Tin học trẻ 2021 - Vòng khu vực - Bảng B - Kho báu}$
-----
###### 🔗 Link: [https://oj.vnoi.info/problem/tht21_kvb_treasure](https://oj.vnoi.info/problem/tht21_kvb_treasure)
###### 📌 Tags: `Backtrack`, `Brute-forces`, `Meet In The Middle`, `DP-Knapsack`, `DP-Space Optimized`
###### 🛠 Work: 7+ hours
###### 👤 Writer: @matchamachiato, @deptrai2k7, @SPyofgame
###### 👥 Contributor: @eggdacoder2006, @[Editorial Slayers Team](https://hackmd.io/@Editorial-Slayers)
###### 📋 Content:
[TOC]
-----
## Subtask 1
> [color=lightgreen] Tags: `Backtrack`
Ở subtask này, vì $n \le 12$ nên ta hoàn toàn có thể sinh dãy tam phân hoặc gọi đệ quy như `dfs` để xét từng trường hợp.
Vì $3^{12} = 531441 \le 10^{6}$ nên độ phức tạp $3^{n}$ có thể chấp nhận được.
-----
> **Time:** $O(3^{n})$
> **Space:** $O(n)$
> **Algo:** `Brute force`, `Backtrack`
> [color=lightgreen]
:::success
:::spoiler Duy_e Code
```cpp=
/*
/// Author comment:
Author: Duy_e
Solution:
This solution will be implement with recursive, it's just similar to regular DFS.
We will have a Backtrack function with the following parameter:
Backtrack(left_bound, right_bound, value_of_A, value_of_B, value_being_sell)
*/
#include <iostream>
using namespace std;
const int N = 13;
const int inf = 1e9;
int v[N], n, ans = inf;
void backtrack(int L, int R, int V_a, int V_b, int V_s){
if (L > R) { // out of array
/*
This mean we have itterated through all element of the array
Now just update the answer
*/
if (V_a == V_b)
ans = min(ans, V_s);
return;
}
// 3 case of recursive:
// Case 1: give one to Alice
backtrack(L + 1, R, V_a + v[L], V_b, V_s);
// Case 2: give one to Bob
backtrack(L + 1, R, V_a, V_b + v[L], V_s);
// Case 3: sell this one
backtrack(L + 1, R, V_a, V_b, V_s + v[L]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*
This task requires reading the unknown amount of input,
so when you compile in your computer remember to input by files.
#define file "test"
#ifndef ONLINE_JUDGE
freopen(file".inp","r",stdin);
freopen(file".out","w",stdout);
#endif
*/
while (cin >> n){
for (int i = 1; i <= n; i ++)
cin >> v[i];
ans = inf;
backtrack(1, n, 0, 0, 0);
cout << ans << '\n';
}
return 0;
}
```
:::
:::success
:::spoiler kazamahoang Code
```cpp=
template<typename T> bool minimize(T& a, const T& b) {
if (a > b) {a = b; return true;} return false;
}
int n, a[105];
namespace sub1 {
ll res, total;
void gen(int pos, int s, int t) {
if (pos == n + 1) {
if (s == t) minimize(res, total - s - t);
return;
}
gen(pos+1, s+a[pos], t);
gen(pos+1, s, t+a[pos]);
gen(pos+1, s, t);
}
void solve() {
total = 0;
for (int i = 1; i <= n; ++ i) total += a[i];
res = inf;
gen(1, 0, 0);
cout << res << "\n";
}
}
```
:::
:::success
:::spoiler SPyofgame Code
```cpp=
#include <iostream>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int LIM = 100;
int n;
int a[LIM];
ll subtask1()
{
ll res = +LINF;
for (int mask = 0; mask < (1 << n); ++mask) /// For each way to split to 2 groups (select / delete)
{
for (int submask = mask; ; submask = (submask - 1) & mask) /// For each way to split to 3 groups (Alice / Bob) / (delete)
{
ll v1 = 0, v2 = 0, v3 = 0; /// Sum of each group
for (int i = 0; i < n; ++i) /// For each element
{
int x = a[i + 1];
if (mask >> i & 1) /// Select
{
if (submask >> i & 1)
{
/// Add to group 1 (Alice)
v1 += x;
}
else
{
/// Add to group 2 (Bob)
v2 += x;
}
}
else
{
/// Add to group 3 (remove)
v3 += x;
}
}
if (v1 == v2) minimize(res, v3);
if (submask == 0) break;
}
}
return res;
}
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
while (cin >> n)
{
for (int i = 1; i <= n; ++i) cin >> a[i];
cout << subtask1() << "\n";
}
return 0;
}
```
:::
#### Bonus:
Nếu bạn nào muốn dùng bitmask để duyệt thay vì sinh tam phân hoặc gọi đệ quy thì có thể xem thêm phần "Duyệt qua tất cả tập con" của vnoi ở đây [LINK](https://vnoi.info/wiki/translate/topcoder/fun-with-bits.md#t%E1%BA%A5t-c%E1%BA%A3-c%C3%A1c-t%E1%BA%ADp-con). Việc này giúp giảm constant time, do đó code sẽ chạy nhanh hơn.
-----
-----
-----
-----
-----
## Subtask 2
:::info
:::spoiler Hướng dẫn chi tiết của SPyofgame
Đây là subtask được cho nhằm tối ưu thuật toán `back track` ở subtask trước vì với $n \le 24$ thì ta không thể sinh đủ dãy tam phân có $n$ phần tử trong thời gian cần thiết được.
Nhưng nhận thấy rằng khi ta duyệt qua nhiều dãy tam phân như vậy thì phần kết quả đều có phần chung, đó là vì các biến độc lập nhau nên khi ta chọn sẵn $k$ phần tử đầu tiên từ tập $n$ phần tử thì $n - k$ phần tử còn lại tuy có nhiều dãy thỏa mãn, nhưng đều chỉ có một kết quả là tối ưu nhất.
Để dễ hình dung, đầu tiên ta có các định nghĩa như sau:
- Gọi $S$ là một xâu tam phân gồm các giá trị $\{0, 1, 2\}$, là một cách chọn cho $|S|$ phần tử đầu tiên, với các giá trị trong $S$ thể hiện số nhóm của phần tử đó
- Gọi $T$ là một xâu tam phân gồm các giá trị $\{0, 1, 2\}$, là một cách chọn cho $|T|$ phần tử cuối cùng, với các giá trị trong $T$ thể hiện số nhóm của phần tử đó
- Không mất tính tổng quát ta giả sử nhóm $1$ là nhóm của $Alice$, nhóm $2$ là nhóm của $Bob$ và nhóm bị loại bỏ là nhóm $0$,
- $D(S)$ là tổng độ chênh lệch giữa tổng hai nhóm trong $S$
- $V(S)$ là tổng các phần tử bị loại bỏ trong $S$
Ta có được một thuật toán đơn giản như sau
- Khi $D(S) = D(T)$ có nghĩa là nếu ta đảo nhóm $1$ với nhóm $2$ trong tập $S$ hoặc tập $T$, thì cách chọn hiện tại sẽ cho $2$ nhóm chọn được các phần tử có tổng bằng nhau
- Tổng các phần bị bỏ sẽ là $V(S) + V(T)$
- Kết quả của bài toán là $res = min(V(S) + V(T))$ với các tập $S, T$ thỏa $D(S) = D(T)$
Nếu chỉ đến đây, ta sẽ có độ phức tạp là $O(|S| \times |T|)$
-----
Gọi $C_k(S)$ là các giá trị $V(S)$ có $k = D(S)$ , ta có thể sắp xếp các cặp theo giá trị $D(S)$ tăng dần để có thể biết được các giá trị $V(S)$ có cùng $D(S)$ trong $O(C_{D(S)}(S))$
Tuy nhiên độ phức tạp lại thành $O(|S| \log |S| \times |T| \log |T|)$
Ta có thể tối ưu bằng cách cố định $k$, ta cũng dễ biết được
- Gọi $res_k = min(V(S) + V(T))$ với $k = D(S) = D(T)$ và kết quả bài toán $res = min(res_k)$
- Vì với mỗi tập $S$, ta chỉ cho ra duy nhất một kết quả $D(S)$ và $V(S)$ và ta không cần quan tâm cách chia tập nên ta có thể chia các tập $S$ thành $O(|S|)$ cặp $\{D(S), V(S)\}$ phân biệt
- Ta cũng có thể làm tương tự với $T$
Gọi $O(F_k(S)) = O\left(C_k(S) \log C_k(S)\right)$ là độ phức tạp khi sắp xếp từng dãy
Lúc này độ phức tạp từ $O(|S| \log |S| \times |T| \log |T|) = O( \Sigma(F_k(S)) \times \Sigma (F_k(T)))$ thành $O(\Sigma (F_k(S) \times F_k(T)))$
Nhìn có vẻ có thêm phần $O(log)$ thì làm chậm chương trình, nhưng trong trường hợp tổng quát thì nhanh hơn nhiều, và tất nhiên cũng có thể tối ưu để nó cũng nhanh hơn trong mọi trường hợp
-----
Cuối cùng, một bước đơn giản thôi
- $res_k = min(V(S) + V(T)) = min(V(S)) + min(V(T))$
Vì sau khi sắp xếp các cặp theo $D(S)$, ta biết các giá trị $V(S)$ có cùng $D(S)$ rồi, nên ta cũng có thể tính $min(V(S))$ trong $O(1)$ với mọi $D(S)$
Lúc này độ phức tạp từ $O(\Sigma (C_k(S) \times C_k(T)))$ thành $O( \Sigma(F_k(S)) + \Sigma (F_k(T))) = O(|S| \log |S| + |T| \log |T|)$
Ta đã tối ưu từ $O(|S| \times |T|) = O(3^n \times 3^{n - k})$ sang $O(|S| + |T|) = O(3^n + 3^{n-k})$
Ta đạt được độ phức tạp tối ưu khi chia dãy sao cho $|n - k| \leq 1$, khi này $O(|S| + |T|) = O(3^{\left \lceil n/2 \right \rceil})$
:::
Đây là subtask được cho nhằm tối ưu thuật toán `back track` ở subtask trước. Với $n \le 24$ thì ta không thể sinh đủ dãy tam phân có $n$ phần tử được. Nhưng nhận thấy rằng khi ta duyệt qua nhiều dãy tam phân như vậy thì phần kết quả đều có phần chung. Cụ thể là ta sẽ
Bằng cách chia đôi tập các vật, ta có thể xử lí riêng trên mỗi tập và sau đó `merge` lại.
Tiếp cận:
- Mỗi vật có ba lựa chọn: đưa cho Alice, đưa cho Bob hoặc bán đi.
- Giả sử:
- Ở tập thứ nhất, Alice được đưa cho các vật có tổng ước giá là $x_1$ , Bob được đưa cho các vật có tổng ước giá là $y_1$
- Ở tập thứ hai, Alice được đưa cho các vật có tổng ước giá là $x_2$ , Bob được đưa cho các vật có tổng ước giá là $y_2$
- Để tổng ước giá các vật bằng nhau thì $x_1 + x_2 = y_1 + y_2$. Hay $x_1 - y_1 = y_2 - x_2$.
- Vậy tập thứ nhất cần lưu hiệu giữa $x_1$ và $y_1$, cũng như tổng ước giá của các vật bán đi (còn lại). Với mỗi dãy tam phân ở tập thứ hai, ta có thể tính toán kết quả bằng cách kiểm tra xem trong tập thứ nhất có tồn tại tổng $y_2 - x_2$ hay không. Trong các khả năng tồn tại $y_2 - x_2$, ta chọn khả năng cho ta tổng ước giá các vật bán đi (còn lại) là nhỏ nhất.
-----
Với $m = \left \lceil \frac{n}{2} \right \rceil$.
> **Time:** $O(3^m \times \log_2(3^m))$
> **Space:** $O(3^m)$
> **Algo:** `Meet In The Middle`
> [color=lightgreen]
:::success
:::spoiler Duy_e Code
```cpp=
namespace sub2{
// f.st = chênh lệch = u - v, f.nd = bỏ
ll ans;
void backtrack(ll l, ll r, pii f, bool ok){
if (l > r){
if (ok) {
int l = 0, r = second.size() - 1, mid, res = 0;
while (l <= r){
mid = l + r >> 1;
if (second[mid].st >= -f.st)
res = mid, r = mid - 1;
else
l = mid + 1;
}
if (second[res].st == -f.st)
ans = min(ans, f.nd + second[res].nd);
} else second.push_back(f);
return;
}
backtrack(l + 1, r, {f.st + a[l], f.nd}, ok);
backtrack(l + 1, r, {f.st - a[l], f.nd}, ok);
backtrack(l + 1, r, {f.st, f.nd + a[l]}, ok);
}
void solve(){
store.clear();
second.clear();
ans = oo;
if (n == 1) {
cout << a[1] << '\n';
return;
}
backtrack(n/2 + 1, n, {0, 0}, 0);
// cout << ans << ' ';
sort(second.begin(), second.end());
backtrack(1, n/2, {0, 0}, 1);
cout << ans << '\n';
}
}
```
:::
:::success
:::spoiler kazamahoang Code
```cpp=
namespace sub2 {
pair<ll, ll> p[1000005];
int cnt;
ll res;
void back_track(int pos, int en, ll x = 0, ll y = 0, ll sum = 0) {
if (pos == en) {
if (en != n + 1) {
p[++cnt] = {x-y, sum-x-y}; // lưu hiệu x1-y1 và tiền bán đi
} else {
int u = lower_bound(p + 1, p + 1 + cnt, make_pair(y-x, -INF)) - p;
if (u == cnt + 1 || p[u].F != y-x) return; // không tồn tại
res = min(res, p[u].S + sum - x - y);
}
return;
}
// đưa cho Alice
back_track(pos+1, en, x+a[pos], y, sum+a[pos]);
// đưa cho Bob
back_track(pos+1, en, x, y+a[pos], sum+a[pos]);
// bán đi
back_track(pos+1, en, x, y, sum+a[pos]);
}
void solve() {
if (n == 1) {
cout << a[1] << "\n";
return;
}
cnt = 0; res = INF; // khởi tạo giá trị
int m = (1 + n) / 2;
back_track(1, m + 1); sort(p + 1, p + 1 + cnt); // chuẩn bị tập m số đầu tiên
back_track(m + 1, n + 1); // tính toán kết quả
cout << res << "\n";
}
}
```
:::
:::success
:::spoiler SPyofgame Code
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
const int LIM = 100;
template<typename T>
void gets(vector<T> &S, int n, int a[])
{
S.reserve(1 << int(double(1.585) * n)); /// Arround this much
for (int mask = 0; mask < (1 << n); ++mask) /// For every possible way to split to 2 groups
{
for (int submask = mask; ; submask = (submask - 1) & mask) /// For every possible way to split to 3 groups
{
ll d = 0, v = 0;
for (int i = 0; i < n; ++i)
{
int x = a[i + 1];
if (mask >> i & 1)
{
if (submask >> i & 1)
d += x; /// Group 1
else
d -= x; /// Group 2
}
else v += x; /// Deleted Item
}
if (d < 0) d *= -1; /// With out loss of generality
S.emplace_back(d, v);
if (submask == 0) break;
}
}
/// Allow two-pointer / binary search
sort(all(S));
/// (d, x) is not optimal as (d, y) for all (x > y)
/// Remove all pair(d, v) that have higher (v)
S.erase(unique(all(S), [](const T& a, const T& b) {
return a.first == b.first;
}), S.end());
}
int n, m, k;
int a[LIM];
int l[LIM];
int r[LIM];
int subtask2()
{
/// Split to two slightly equal parts
k = n / 2, m = n - k, n = k;
for (int i = 1; i <= k; ++i) l[i] = a[i];
for (int i = 1; i <= m; ++i) r[i] = a[i + k];
/// Left part and Right part
vector<pair<ll, ll> > LT;
vector<pair<ll, ll> > RT;
/// Get all possible choice -> (different of two groups, sum of deletion)
gets(LT, n, l);
gets(RT, m, r);
/// Two Pointer
/// Find minimum (sum of deletion) for (different of two groups = 0)
/// <-> Find minimum (sum of deletion in left part) + (sum of deletion in right part)
/// satisfied (diffrent of left group - diffeent of right group = 0)
///
ll res = +LINF;
for (int i = 0, j = 0; i < LT.size(); ++i) /// For each element in left part
{
while (j < RT.size() && RT[j].first < LT[i].first) ++j; /// Right part is smaller
if (j == RT.size()) break;
if (LT[i].first == RT[j].first) /// Valid parts
minimize(res, LT[i].second + RT[j].second); /// Find mimal sum of deletion
}
return res;
}
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// For each query
while (cin >> n)
{
if (n > 24) exit(1);
/// Subtask 1-2
for (int i = 1; i <= n; ++i) cin >> a[i];
cout << subtask2() << "\n";
}
return 0;
}
:::
-----
## Subtask 3
Từ subtask 3, ta phải thay đổi thuật toán bởi vì $n$ lớn và $a_i$ nhỏ hơn nhiều so với hai subtask trên.
Một thuật toán có thể dùng đó là `DP-knapsack` hay là quy hoạch động cái túi.
Thông thường `DP-knapsack` sẽ lưu một chiều là trọng lượng của túi. Nhưng ở đây ta có hai người nên ta sẽ dùng hai chiều, một để lưu giá trị vật phẩm của Alice, một để lưu giá trị vật phẩm Bob.
-----
### Tiếp cận:
Gọi `dp[i][V_A][V_B]` là giá trị nhỏ nhất sẽ bỏ ra để Alice nhận số vật phẩm có giá trị là `V_A` và Bob nhận được số vật phẩm có giá trị là `V_B` khi vật cuối cùng được mua là vật thứ `i`.
Do ban đầu cả hai không có vật phẩm nào nên hàm cơ sở `dp[0][0][0] = 0`.
Các hàm còn lại ta khởi tạo bằng `inf`.
Nếu hiện tại ta xét đến vật thứ `i`, Alice có số vật phẩm có ước giá `V_A`
và Bob có số vật phẩm có ước giá `V_B` thì quan hệ giữa các hàm sẽ như sau:
- Thêm cho Alice một vật phẩm:
`dp[i + 1][A_v + v[i + 1]][V_B] = min(dp[i + 1][A_v + v[i + 1]][V_B], dp[i][V_A][V_B])`
- Thêm cho Bob một vật phẩm:
`dp[i + 1][A_v][V_B + v[i + 1]] = min(dp[i + 1][A_v][V_B + v[i + 1]], dp[i][V_A][V_B])`
- Không thêm cho ai cả:
`dp[i + 1][A_v][V_B] = min(dp[i + 1][A_v][V_B], dp[i][V_A][V_B] + v[i + 1])`
-----
### Tối ưu không gian
Vì quy hoạch động chỉ xét $f[i + 1]$ dựa trên $f[i]$ nên những phần $f[i-1], f[i-2], \dots$ trở xuống ta có thể trực tiếp ghi đè dữ liệu lên
-----
### Code:
> Với $S$ là tổng của các phần tử trong $a[]$
> **Time:** $O(n \times S^2)$
> **Space:** $O(2 \times S^2)$
> **Algo:** `DP-knapsack`, `DP- Space Optimized`
> [color=lightgreen]
:::success
:::spoiler kazamahoang Code
```cpp=
namespace sub3 {
ll dp[2][2500][2500];
int s = 0;
void solve() {
for (int i = 1; i <= n; ++ i) s += a[i];
s /= 2;
memset(dp[0], 0x3f, sizeof dp[0]);
dp[0][0][0] = 0;
for (int i = 1; i <= n; ++ i) {
int cur = i&1;
int pre = !cur;
for (int j = 0; j <= s; ++ j)
for (int h = 0; h <= s; ++ h) {
dp[cur][j][h] = INF;
if (j >= a[i])
minimize(dp[cur][j][h], dp[pre][j-a[i]][h]);
if (h >= a[i])
minimize(dp[cur][j][h], dp[pre][j][h-a[i]]);
minimize(dp[cur][j][h], dp[pre][j][h] + a[i]);
}
}
ll res = INF;
for (int i = 0; i <= s; ++ i)
minimize(res, dp[n&1][i][i]);
cout << res << "\n";
}
}
```
:::
-----
## Subtask 4
### Ý tưởng
Từ subtask 3, ta đã biết về cách `DP-knapsack` với hai chiều chứa giá trị, tạm gọi là hai túi. Lúc này nếu dùng cách quy hoạch động trên số lượng trường hợp cần xét ở mỗi vật phẩm $i$ sẽ là $W_A \times W_B$, với $W_A$ và $W_B$ là trọng lượng tối đa ta sẽ xét ở mỗi túi của $A$ và $B$.
Rõ ràng là với độ phức tạp lớn như vậy hoàn toàn không thể qua được subtask 4.
Ta có nhận xét: Hai người chia được, khi có thể phân thành ba tập, trong đó có hai tập có chênh lệch giá trị là $0$ và tập còn lại sẽ là tập bỏ đi.
Từ nhận xét trên, ta biết ở mỗi giai đoạn số tài sản của mỗi người sẽ có một lượng chênh lệch, và ta cần làm lượng này bằng $0$ đồng thời cực tiểu hóa giá trị tập bỏ đi.
Lúc này ta có thể quy hoạch động theo chênh lệch và số lượng trường hợp cần xét sẽ chỉ còn $W_A + W_B$ tập giá trị sẽ từ $[-W_B.. W_A]$.
-----
### Hướng dẫn giải
Lúc này ta sẽ không quy hoạch động theo giá trị, mà sẽ quy hoạch động theo chênh lệch giữa hai tập giá trị.
Gọi hàm ```dp[i][delta]``` là giá trị nhỏ nhất của tập bỏ đi khi xét đến phần tử thứ ```i``` và chênh lệch giá trị của hai tập còn lại là ```delta```.
Ở đây `delta = Value_of_Alice - Value_of_Bob`
Do ban đầu cả hai người đều không có bất kì vật phẩm nào nên ta có hàm cơ sở: `dp[0][0] = 0`.
Các hàm còn lại ta khởi tạo bằng `inf`.
Với `dp[i][delta]`, ta có thể thấy `dp[i + 1][delta + v[i+1]]`, `dp[i+1][delta - v[i-1]]` và`dp[i + 1][delta]` sẽ cần dùng tên đến hàm `dp[i][delta]`.
Ta duyệt `i` từ `0` đến `n-1`, phần chuyển dịch (transition) giữa các hàm sẽ như sau:
- Thêm một phần tử cho Alice:
`dp[i + 1][delta + v[i + 1]] = min(dp[i][delta], dp[i + 1][delta + v[i + 1]])`.
- Thêm một phần tử cho Bob:
`dp[i + 1][delta - v[i + 1]] = min(dp[i][delta], dp[i + 1][delta - v[i + 1]])`.
- Không thêm cho ai, bỏ vào tập để bán:
`dp[i + 1][delta] = min(dp[i][delta] + v[i + 1], dp[i + 1][delta])`.
Lúc này, kết quả bài toán sẽ là `dp[n][0]`.
***Một số lưu ý:***
- vì `delta` có thể âm, nếu ngôn ngữ lập trình không hỗ trợ chỉ số âm thì bạn cần gấp đôi bảng và luôn giữ `delta` luôn không âm. Một cách có thể đó là cộng thêm biến `offset` vào `delta`.
- Từ cách làm trên, độ phức tạp bộ nhớ sẽ là $O(n \times 2 \times sum_v)$ và ta sẽ bị quá bộ nhớ. Ta nhận thấy hàm `dp` ở mỗi `i` chỉ dùng hai tầng là dùng tầng `i` để tính tầng `i + 1`. Từ đây ta có thể tối ưu bộ nhớ chỉ lưu `dp[2][2*sum_v]`.
-----
> Với $S$ là tổng của các phần tử trong $a[]$
> **Time:** $O(n \times S)$
> **Space:** $O(2 \times S)$
> **Algo:** `DP-knapsack`, `DP-Space Optimized`
> [color=lightgreen]
:::success
:::spoiler Duy_e Code
```cpp=
/*
Author: Duy_e
Optimization: Offset trick, space optimization trick
*/
#include <iostream>
using namespace std;
const int N = 100;
const int inf = 1e9;
const int offset = 1e5;
// a = min(a, b)
void minimize(int &a, int b){
if (a > b) a = b;
}
int dp[2][offset*2], v[N], sum_v, n;
void solve_sub_4(){
sum_v = 0;
for (int i = 1; i <= n;i ++)
sum_v += v[i];
// assign and base case:
for (int i = -sum_v; i <= sum_v; i ++)
dp[0][i + offset] = dp[1][i + offset] = inf;
dp[0][0 + offset] = 0;
for (int i = 0; i < n; i ++){
// two consecutive layers
int layer_1 = i % 2, layer_2 = 1 - layer_1;
for (int w = -sum_v; w <= sum_v; w ++){
minimize(dp[layer_2][w + v[i + 1] + offset ], dp[layer_1][w + offset]);
minimize(dp[layer_2][w - v[i + 1] + offset ], dp[layer_1][w + offset]);
minimize(dp[layer_2][w + offset], dp[layer_1][w + offset] + v[i + 1]) ;
// reset layer i for ready to become layer i + 2
dp[layer_1][w+offset] = 1e9;
}
}
cout << dp[n % 2][0 + offset] << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*
This task requires reading the unknown amount of input,
so when you compile in your computer remember to input by files.
#define file "test"
#ifndef ONLINE_JUDGE
freopen(file".inp","r",stdin);
freopen(file".out","w",stdout);
#endif
*/
while (cin >> n){
for (int i = 1; i <= n; i ++)
cin >> v[i];
solve_sub_4();
}
return 0;
}
```
:::
:::success
:::spoiler kazamahoang Code
```cpp=
namespace sub4 {
const int base = 5e4;
ll dp[2][100005];
int s = 0;
void solve() {
for (int i = 1; i <= n; ++ i) s += a[i];
s /= 2;
memset(dp[0], 0x3f, sizeof dp[0]);
dp[0][base] = 0;
for (int i = 1; i <= n; ++ i) {
int cur = i&1;
int pre = !cur;
for (int j = -s; j <= s; ++ j) {
dp[cur][j+base] = INF;
if (j + a[i] <= s)
minimize(dp[cur][j+base], dp[pre][j+a[i]+base]);
if (j - a[i] >= -s)
minimize(dp[cur][j+base], dp[pre][j-a[i]+base]);
minimize(dp[cur][j+base], dp[pre][j+base] + a[i]);
}
}
cout << dp[n&1][base] << "\n";
}
}
```
:::
:::success
:::spoiler SPyofgame Code
```cpp=
#include <algorithm>
#include <iostream>
#include <cstring>
#include <bitset>
#include <vector>
#include <cmath>
using namespace std;
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
const int LIM_N = 100;
const int LIM_A = 1010;
const int LIM_S = LIM_N * LIM_A;
int n, m, k;
int a[LIM_N];
int f[2][2 * LIM_S + 1];
int subtask4()
{
int S = 0;
for (int i = 1; i <= n; ++i)
S += a[i];
for (int t = -S; t <= +S; ++t)
f[0][t + LIM_S] = f[1][t + LIM_S] = +INF;
f[0 & 1][0 + LIM_S] = 0;
for (int i = 1; i <= n; ++i)
{
bool cur = i & 1;
bool pre = !cur;
for (int t = -S; t <= +S; ++t)
{
minimize(f[cur][t + a[i] + LIM_S], f[pre][t + LIM_S]);
minimize(f[cur][t - a[i] + LIM_S], f[pre][t + LIM_S]);
minimize(f[cur][t + LIM_S], f[pre][t + LIM_S] + a[i]);
f[pre][t + LIM_S] = +INF;
}
}
return f[n & 1][0 + LIM_S];
}
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// For each query
while (cin >> n)
{
for (int i = 1; i <= n; ++i) cin >> a[i];
cout << subtask4() << "\n";
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet