---
title
Đề thi thử TS10
---

Đề thi thử TS10
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Bài 1: Leo núi

2SG vừa tổ chức một cuộc thi leo núi. Trong cuộc thi này có $M$ thí sinh tham gia. Sau khi cuộc thi kết thúc, BTC sẽ thực hiện trao giải theo độ cao mỗi thí sinh đang đứng. Tuy nhiên, trong quá trình ghi nhận kết quả gặp một số trục trặc nên đã không lưu lại độ cao mà chỉ lưu lại vị trí của từng người trên bảng đồ. Được biết núi là một ma trận $N \times N$ dạng kim tự tháp có cấu trúc như sau:
- Lớp bên ngoài cùng có độ cao là $1$.
- Lớp thứ hai có độ cao là $2$.
- ...
- Lớp trong cùng có độ cao là $\lfloor\frac{N+1}{2}\rfloor$.
> Hình trên là minh họa của núi trong cuộc thi, ví dụ ô $(3, 2)$ có độ cao là $2$.

Với danh sách vị trí của $M$ thí sinh, hãy giúp BTC cuộc thi tìm độ cao mà mỗi thí sinh đang đứng.

## Input
- Dòng đầu gồm hai số nguyên dương $N$ và $M$ lần lượt là kích thước của núi và số thí sinh tham gia. $(1 \le M \le 10^6, 1 \le N \le 10^9)$.
- $M$ dòng kế tiếp là hai số nguyên $x_i, y_i$ là vị trí mà thí sinh đang đứng trên ma trận $(1 \le x_i, y_i \le N)$.
## Output
- Gồm $M$ dòng, dòng thứ $i$ chứa một số nguyên độ cao mà thí sinh thứ $i$ đang đứng.
## Subtask
- Có $60\%$ số test ứng với $60\%$ số điểm thỏa mãn: $N \le 1000$.
- $40\%$ số test còn lại ứng với $40\%$ số điểm: Không có ràng buộc gì thêm
## Sample Input

6 4
1 1
2 3
4 3
5 2

## Sample Output

1
2
3
2

## Solution

:::spoiler Hướng dẫn giải
- Ta nhận thấy giá trị của mỗi ô bằng số lớp bao lấy ô đó. Các lớp sẽ duy chuyển từ ngoài vào trong $\Rightarrow$ giá trị mỗi ô sẽ phụ thuộc khoảng cách gần nhất của ô đó đến mép ngoài cùng của bảng. Ô $(i, j)$ sẽ có giá trị là $min(i, j, n - i + 1, n - j + 1)$.
:::

::: spoiler Cài đặt

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        cout << min({x, y, n - x + 1, n - y + 1}) << endl;
    }
    return 0;
}

:::

# Bài 2: Truy tìm tội phạm
## Đề bài
- Cảnh sát bắt đầu thu thập bằng chứng điều tra về một số vụ án vừa xảy ra gần đây. Manh mối tìm được là những dấu chân ở hiện trường các vụ án, được biểu diễn bằng một dãy gồm các kí tự '$)$' (dấu chân phải) và '$($' (dấu chân trái). Bạn là một chuyên gia về xử lý các manh mối bằng công nghệ, do đó, cảnh sát mời bạn tham gia giải quyết vụ án này.
- Nhiệm vụ của bạn là xử lý hiện tượng nhiễu thông tin manh mối. Sau khi nghiên cứu các dữ liệu được gửi về, bạn đã nghĩ ra một phương pháp sàng lọc bằng máy tính như sau:
- Với mỗi bước thực hiện, máy tính sẽ xóa bỏ một số dấu chân nếu phát hiện chuỗi dấu chân đó là **tiền tố nhiễu**.
- **Tiền tố nhiễu** là một chuỗi dấu chân nằm ở đầu dãy, thỏa mãn một trong hai điều kiện sau:
- Các dấu chân trong chuỗi có thể được chia ra thành các cặp dấu chân, mỗi cặp gồm một dấu chân trái và một dấu chân phải và trong một cặp, dấu chân trái có vị trí trước dấu chân phải trong chuỗi gốc. Ví dụ, các chuỗi thỏa điều kiện: $'(())()'$, $'()'$, $'(()(()))'$; các chuỗi không thỏa điều kiện: $')('$, $'(()'$, $'(()))('$,
- Chuỗi đó là một chuỗi đối xứng (khi viết chuỗi gốc theo thứ tự từ đuôi lên đầu, ta thu được chuỗi mới giống chuỗi gốc). Ví dụ, các chuỗi đối xứng: $'))'$, $'(('$, $')(()'$; các chuỗi không đối xứng: $'()'$, $')('$, $'))('$
- Chương trình sẽ dừng chạy khi không tìm thấy tiền tố nhiễu nào nữa.

- Bạn phải xử lý dữ liệu cho $t$ vụ án.

## Input
- Dòng đầu gồm số nguyên $t$ $(1 \le t \le 10^4)$, số vụ án. $2t$ dòng tiếp theo mô tả dữ liệu mỗi vụ án.
- Dòng đầu tiên của mỗi vụ án chứa giá trị $n$, độ dài chuỗi bước chân $(1 \le n \le 500000)$
- Dòng thứ hai chứa chuỗi gồm $n$ kí tự '$)$' (dấu chân phải) và '$($' (dấu chân trái)
- Dữ liệu đảm bảo tổng của $n$ trong các vụ án không vượt quá $500000$

## Ouput
- Với mỗi vụ án, in ra 2 số nguyên lần lượt là số thao tác xóa tiền tố nhiễu và số kí tự còn lại của dãy sau khi thực hiện các thao tác.

## Sample Input

5
2
()
3
())
4
((((
5
)((()
6
)((()(

## Sample Output

1 0
1 1
2 0
1 0
1 1

:::

## Solution
**Lưu ý:** Vì có đến $10^4$ test nên nên để tránh **chạy quá thời gian** khi in kết quả bài toán, ta phải sử dụng `\n` để xuống dòng thay vì `endl`.
:::spoiler Ý tưởng
- Vì mỗi lần xoá, ta xoá xâu tiền tố **ngắn nhất có thể** thoả mãn điều kiện đề bài, nên ta suy ra được **3** trường hợp:
+ **Trường hợp 1:** Xâu tiền tố ngắn nhất xoá được là '$(($' hoặc '$))$', thoả điều kiện xâu tiền tố được xoá phải *đối xứng* và có độ dài ít nhất là $2$.
+ **Trường hợp 2:** Xâu tiền tố ngắn nhất xoá được là '$()$', thoả điều kiện xâu tiền tố được xoá phải là một *dãy ngoặc đúng* và có độ dài ít nhất là $2$.
+ **Trường hợp 3:** Xâu tiền tố ngắn nhất xoá được có dạng '$)(...)$', với các kí tự trong '$...$' là một số lượng'$($' bất kì. **VD:** '$)()$', '$)(((()$'.
- Ngoài ra ta cũng cần phải lưu ý là nếu xâu đề bài cho có độ dài là 1 thì ta không thể thực hiện bất kì lần xoá xâu tiền tố nào.
- Đây là một bài tập dạng tham lam và yêu cầu một chút sự kĩ lưỡng trong khâu cài đặt.
:::

:::spoiler Code mẫu

#include <bits/stdc++.h>
using namespace std;

int n, cnt, pos;
bool flag;
string s;

void Solve()
{
    cin >> n >> s;
    if (n == 1)
    {
        cout << "0 1" << "\n";
        return;
    }
    cnt = flag = 0;
    pos = -1; // Lưu vị trí cuối cùng được xoá để tính toán độ dài của xâu còn lại sau các lần xoá
    int i = 0;
    while (i < n)
    {
        if (!flag && ((s[i] == s[i + 1]) || (s[i] == '(' && s[i + 1] == ')'))) // Trường hợp 1 và 2
        {
            pos = i + 1;
            cnt++;
            i += 2;
        }
        else if (flag && s[i] == ')') // Điểm bắt đầu và kết thúc của trường hợp 3
        {
            pos = i;
            cnt++;
            flag = 0;
            i++;
        }
        else // Phần ở giữa của trường hợp 3
        {
            flag = 1;
            i++;
        }
    }
    cout << cnt << " " << n - pos - 1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) Solve();
    return 0;
}

:::

# Bài 3: Trận đấu hấp dẫn

## Đề bài
- Một trận đấu gồm $N$ người tham gia đứng cạnh nhau thành 1 hàng với $a_i \space (1 \le i \le n)$ là sức mạnh của mỗi người.
- Để hấp dẫn nhiều khán giả đến xem, trận đấu cần chọn ra số người chơi xếp cạnh nhau nhiều nhất sao cho có thể chia các người chơi thành 2 đội bằng cách đặt 1 tấm bảng ở giữa để chia thành 1 đội bên trái và 1 đội bên phải và tổng sức mạnh của mỗi đội là như nhau
- Tìm cách chọn các người chơi để trận đấu hấp dẫn nhất có thể

## Input
- Dòng đầu gồm số nguyên $N$ $(2 \le N \le 5000)$
- $N$ dòng tiếp theo, dòng thứ $i$ chứa giá trị của phần tử $a_i$ của dãy $(0 \le a_i \le 200000)$

## Ouput
- 1 dòng duy nhất là số người chơi nhiều nhất sắp xếp được sao cho trận đấu trở nên hấp dẫn nhất

## Sample Input

6
2
10
3
2
5
1

## Sample Output

4

## Subtask
- $40\%$ số test tương ứng với $40\%$ số điểm thỏa mãn: $N \le 500$
- $60\%$ số test còn lại tương ứng với $60\%$ điểm không có ràng buộc gì thêm

## Solution
:::spoiler Hướng dẫn giải
- *Subtask 1:*
- Với $N \le 500$, ta thấy rằng có thể duyệt qua từng đoạn con của mảng và duyệt qua từng vị trí trong đoạn con đó để kiểm tra xem có thể chia đoạn con đó thành 2 đoạn con bằng nhau được hay không. Nếu đoạn con này thỏa thì cập nhật lại độ dài đoạn con lớn nhất tìm được.
- Độ phức tạp: $O(n^3)$
- *Subtask 2:*
- Cách 1: Ta sẽ duyệt qua các độ dài $len$ giảm dần từ $n \to 2$. Với mỗi $len$, ta sẽ duyệt vị trí bắt đầu $l$ từ $1$ đến $n - len + 1$. Ta cần kiểm tra xem đoạn con $[l, l + len - 1]$ có thoả mãn hay không, điều đầu tiên ta cần kiểm tra sẽ là tổng của dãy con đấy phải chia hết cho 2, nếu thoả mãn ta tiếp tục sử dụng tìm kiếm nhị phân để tìm vị trí $k$ sao cho $sum(a[l...k]) = sum(a[k + 1...l + len - 1])$, nếu tồn tại một vị trí $k$ thì ta sẽ in ngay độ dài $len$ và kết thúc chương trình bởi vì đấy chính là độ dài lớn nhất của dãy thoả mãn (vì ta duyệt $len$ lùi từ $n \to 2$). Cách này sẽ có độ phức tạp $O(n^2\log{n})$, vừa đủ để qua 50 test của bài với thời gian 0.4s. Tuy nhiên thì trong trường hợp tệ nhất ($n = 5000$, $len = 2$, tổng của mọi dãy con đều chia hết cho $2$) thì cách này có khả năng sẽ bị **TLE**.
- Cách 2: Tương tự subtask 1, ta sẽ duyệt mọi đoạn con $[l, r]$, tuy nhiên thay vì duyệt thêm 1 vòng $k$ để kiểm tra thì ta sẽ rút ra được nhận xét như sau: Cố định $l$, ta thấy $r$ càng tăng thì điểm $k$ thoả mãn $sum(a[l...k]) = sum(a[k+1...r])$ càng tăng. Từ đây ta sẽ sử dụng **2 con trỏ** để tìm $k$. Độ phức tạp ở cách làm này đã giảm xuống $O(n^2)$, đủ sức để qua 50 test với time limit 0.4s.
:::

:::spoiler Code mẫu
Cách 1: Sử dụng tìm kiếm nhị phân

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a[5001], pref[5001];

ll calc(int l, int r) {
    return pref[r] - pref[l - 1];
}

bool binarySearch(int l, int r) {
    int left = l, right = r;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if (calc(left, mid) == calc(mid + 1, right)) return true;
        if (calc(left, mid) > calc(mid + 1, right)) r = mid - 1;
        else l = mid + 1;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    for(int len = n; len >= 2; len--) {
        for(int l = 1; l <= n - len + 1; l++) {
            if(calc(l, l + len - 1) % 2 == 0) {
                if(binarySearch(l, l + len - 1)) {
                    cout << len;
                    return 0;
                }
            }
        }
    }

    cout << 0;
    return 0;
}

Cách 2: Sử dụng 2 con trỏ

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll a[5005], pref[5005];
 
ll calc(int l, int r) {
    return pref[r] - pref[l - 1];
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
    int ans = 0;
    for (int i = 1; i < n; i++) {
        int k = i;
        for (int j = i + 1; j <= n; j++) {
            while (calc(i, k) < calc(k + 1, j)) k++;
            if (calc(i, k) == calc(k + 1, j)) ans = max(ans, j - i + 1);
        }
    }
    cout << ans;
 
    return 0;
}

:::
# Bài 4: Mua quà

- Một cửa hàng nọ có $N$ phần quà được trưng bày cạnh nhau trên kệ hàng. Mỗi phần quà trên kệ hàng đều có giá nhất định, phần quà thứ $i$ có giá $A_i$ đồng. Cửa hàng hiện đang có chương trình khuyến mãi một phần quà đặc biệt **(không nằm trên kệ hàng)** cho những đơn hàng đáp ứng điều kiện sau: Với mỗi phần quà được mua phải có **ít nhất** một phần quà được trưng bày cạnh nó trên kệ hàng cũng được mua. Nói cách khác, nếu phần quà thứ $i$ trên kệ hàng được mua thì phần quà thứ $i-1$ hoặc $i+1$ cũng phải được mua.
- Bạn $A$ dự định sẽ dùng $S$ đồng để mua quà tặng cho bạn của mình, bạn thắc mắc rằng với $S$ đồng trong túi thì có thể mua được nhiều nhất bao nhiêu phần quà trên kệ hàng sao cho tổng giá tiền các phần quà được mua **không vượt quá $S$** mà vẫn nhận được phần quà đặc biệt của cửa hàng. Có $Q$ giả định, với mỗi giả định về số tiền $S$ mà bạn $A$ dự định sẽ dùng để mua quà, hãy viết chương trình giúp bạn tìm được số phần quà nhiều nhất bạn có thể dùng $S$ đồng để mua mà vẫn nhận được phần quà đặc biệt của cửa hàng.

## Input
- Dòng đầu tiên gồm hai số nguyên dương $N, Q$ lần lượt là số lượng phần quà được trưng bày trên kệ hàng và số lượng giả định được bạn $A$ đặt ra $(2 \le N \le 1000; 1 \le Q \le 5 \cdot 10^5)$.
- Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2,...A_N$ lần lượt là giá tiền của từng phần quà theo thứ tự được xếp trên kệ hàng $(1\le A_i \le 10^9, \forall i = 1,2,...,N)$.
- $Q$ dòng tiếp theo, mỗi dòng gồm một số nguyên dương $S$ $(1 \le S \le 10^9)$.
## Output
- Gồm $Q$ dòng, dòng thứ $i$ chứa một số nguyên là đáp án của giả định thứ $i$. Nếu không tồn tại cách mua hàng nào dùng $S$ đồng để có thể nhận được phần quà đặc biệt của cửa hàng thì đáp án là $0$.
## Subtask
- Có $20\%$ số test tương ứng với $20\%$ số điểm thỏa mãn: $N \le 20$.
- $30\%$ số test khác ứng với $30\%$ số điểm thỏa mãn: $N \le 100$.
- $20\%$ số test khác ứng với $20\%$ số điểm thỏa mãn: $S \le 100$.
- $10\%$ số test khác ứng với $10\%$ số điểm thỏa mãn: $Q \le 1000$.
- $20\%$ số test còn lại ứng với $20\%$ số điểm: Không có ràng buộc gì thêm.

## Sample Input

5 3
1 2 3 2 1
3
6
9

## Sample Output

2
4
5

#### Note
- Ở giả định đầu tiên, bạn $A$ sẽ chọn mua $2$ phần quà đầu, tổng số tiền cần phải trả là $1+2=3 \le 3$.
- Ở giả định thứ hai, bạn $A$ sẽ mua hai phần quà đầu tiên và hai phần quà cuối cùng trên kệ hàng. Tổng số tiền cần phải trả là $1+2+2+1 = 6\le 6$.
- Ở giả định thứ ba, bạn $A$ sẽ mua cả $5$ phần quà trên kệ hàng. Tổng số tiền cần phải trả là $1+2+3+2+1 = 9 \le 9$.

## Solution
**Lưu ý:** Vì có đến $5 \cdot 10^5$ truy vấn nên nên để tránh **chạy quá thời gian** khi in kết quả bài toán, ta phải sử dụng `\n` để xuống dòng thay vì `endl`.
### Subtask 1, 2
:::spoiler **Ý tưởng**
- Gọi $dp[i][j]$ là số tiền ít nhất để có thể mua $j$ phần quà mà vẫn nhận được phần quà đặc biệt của cửa hàng, khi xét đến món quà thứ $i$.
- Với mỗi $i, j$ sao cho $j \le i$, ta sẽ thử lấy $k$ phần quà liên tiếp kết thúc tại vị trí $i$, vì ta phải lấy ít nhất 2 phần tử liên tiếp nhau nên $2 \le k \le j$. Công thức quy hoạch động: $dp[i][j]=min(dp[i-k-1][j-k]+sum(i-k+1, i))$ với $sum(x, y) = \sum\limits_{i=x}^ya[i]$. Với mỗi truy vấn, ta sẽ tìm chỉ số $i$ lớn nhất sao cho $dp[n][i] \le S$. Độ phức tạp: $O(N^3+N\cdot Q)$.
:::

:::spoiler **Code**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 1e16));
    
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 0;
        for (int j = 1; j <= i; j++)
        {   
            dp[i][j] = dp[i-1][j];
            long long cost = a[i];
            for (int k = 2; k <= j; k++)
            {
                cost += a[i-k+1];
                long long x = (i-k-1 < 0 ? 0 : dp[i-k-1][j-k]);
                dp[i][j] = min(dp[i][j], x + cost);
            }
        }
    }

    while (q--)
    {
        int s;
        cin >> s;
        for (int i = n; i >= 0; i--)
            if (dp[n][i] <= s)
            {
                cout << i << '\n';
                break;
            }
    }
    return 0;
}

:::

### Subtask 3
:::spoiler **Ý tưởng**
- Gọi $dp[i][j][k]$ là số phần quà trên kệ hàng nhiều nhất có thể mua mà vẫn nhận được phần quà đặc biệt từ cửa hàng với $j$ đồng khi xét đến món quà thứ $i$ và trạng thái là $k$ $(1 \le i \le n; 1 \le j \le 100; 0 \le k \le 2)$. Ý nghĩa của các trạng thái $k$ như sau:
- $k = 0$: Món quà thứ $i$ sẽ không được mua và vẫn nhận được phần quà đặc biệt.
- $k = 1$: Món quà thứ $i$ được mua nhưng món quà thứ $i-1$ không được mua (không nhận được phần quà đặc biệt).
- $k = 2$: Mua ít nhất 2 món quà liên tiếp kết thúc tại vị trí $i$ và vẫn nhận được phần quà đặc biệt.
- Ta có công thức quy hoạch động với từng trạng thái $k$ như sau:
- $k = 0$, $dp[i][j][k] = max(dp[i-1][j][0], dp[i-1][j][2])$.
- $k = 1$, $dp[i][j][k] = dp[i-1][j-a[i]][0]+1$.
- $k = 2$, $dp[i][j][k] = max(dp[i-1][j-a[i]][1], dp[i-1][j-a[i]][2])+1$.
- Như vậy, với mỗi truy vấn, đáp án sẽ là $max(dp[n][s][0], dp[n][s][2])$.
- Độ phức tạp: $O(N \cdot 100 + Q)$. Ngoài ra, kĩ thuật này còn được gọi là quy hoạch động cái túi (knapsack).
:::

:::spoiler **Code**

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 1;
int dp[N][101][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 100; j++)
        {   
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][2]);
            if (j-a[i] >= 0)
            {
                dp[i][j][1] = dp[i-1][j-a[i]][0] + 1;
                if (dp[i-1][j-a[i]][1] > 0)
                    dp[i][j][2] = dp[i-1][j-a[i]][1] + 1;
                if (dp[i-1][j-a[i]][2] > 0)
                    dp[i][j][2] = max(dp[i][j][2], dp[i-1][j-a[i]][2] + 1);
            }
        }

    while (q--)
    {
        int s;
        cin >> s;
        cout << max(dp[n][s][0], dp[n][s][2]) << '\n';
    }
    return 0;
}

:::

### Subtask 4, 5
:::spoiler **Ý tưởng**
- Ở 2 subtask cuối này, ta sẽ kết hợp lời giải từ các subtask trước đó.
- Gọi $dp[i][j][k]$ là số tiền ít nhất để có thể mua $j$ phần quà mà vẫn nhận được phần quà đặc biệt của cửa hàng khi xét đến phần quà thứ $i$ và trạng thái là $k$ $(1 \le j \le i \le n; 0 \le k \le 2)$. Ý nghĩa các trạng thái của $k$ sẽ như **subtask 3**.
- Ta có công thức quy hoạch động với từng trạng thái $k$ như sau:
- $k = 0$, $dp[i][j][k] = min(dp[i-1][j][0], dp[i-1][j][2])$.
- $k = 1$, $dp[i][j][k] = dp[i-1][j-1][0]+a[i]$.
- $k = 2$, $dp[i][j][k] = min(dp[i-1][j-1][1], dp[i-1][j-1][2])+a[i]$.
- Kĩ thuật này còn được gọi là quy hoạch động đảo nhãn, khi ta phải thay đổi các trạng thái của quy hoạch động để tối ưu bài toán, tương tự như bài toán [này](https://oj.vnoi.info/problem/atcoder_dp_e).
- Ở **subtask 4**, với mỗi truy vấn, ta sẽ duyệt và tìm chỉ số $i$ lớn nhất sao cho $min(dp[n][i][0], dp[n][i][2]]) \le S$ với độ phức tạp $O(N^2 + N \cdot Q)$. Còn ở **subtask 5**, chúng ta sẽ cần phải tối ưu thêm.
- Đến đây, sẽ có nhiều bạn dùng kĩ thuật **tìm kiếm nhị phân** để tìm chỉ số $i$ lớn nhất sao cho thỏa mãn điều kiện trên như khi ta làm **subtask 4**, tuy nhiên nếu ta tìm kiếm nhị phân trên dãy min(dp[n][i][0], dp[n][i][2]])thì sẽ không đúng, vì dãy số $min(dp[n][i][0], dp[n][i][2]])$ không thỏa mãn điều kiện tăng dần hoặc giảm dần, vì thế ta không thể **tìm kiếm nhị phân** ở chỗ này được.
- Ta sẽ cần phải xử lý dãy kết quả sau cùng để biến dãy trên thành một dãy đơn điệu, sau đó mới sử dụng **tìm kiếm nhị phân** cho mỗi truy vấn. Độ phức tạp: $O(N^2+(N+Q)\cdot \log_2 N)$. Ngoài ra các bạn có thể sử dụng kĩ thuật hai con trỏ để giảm độ phức tạp bài toán còn $O(N^2 + N \cdot \log_2 N + Q)$.
:::

:::spoiler **Code**

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 1;
long long dp[N][N][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 1e16;
    for (int i = 0; i <= n; i++) dp[i][0][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][2]);
            dp[i][j][1] = dp[i-1][j-1][0] + a[i];
            dp[i][j][2] = min(dp[i-1][j-1][1], dp[i-1][j-1][2]) + a[i];
        }
    }

    long long ans[n + 1] = {0};
    ans[n] = dp[n][n][2];
    for (int i = n-1; i >= 1; i--)
        ans[i] = min(ans[i+1], min(dp[n][i][0], dp[n][i][2]));

    while (q--)
    {
        int s;
        cin >> s;
        cout << upper_bound(ans, ans + n + 1, s) - ans - 1 << '\n';
    }
    
    return 0;
}

:::