Hướng dẫn cho Biểu thức ngoặc (Contest Practice VNOI 2021 Round 5)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 1: \(n \le 10\)
Duyệt tam phân để xét mọi phương án tạo thành biểu thức ngoặc đúng. \(O(3^n)\)
Subtask 2: \(n \le 1000\)
Đặt f(i,j) là giá trị lớn nhất của biểu thức ngoặc khi xét xong \(i\) phần tử đầu tiên của mảng, hiện đang có \(j\) vị trí mở ngoặc chưa có ngoặc đóng tương ứng.
f(0,0) = 0
f(i,j) = f(i-1,j) (bỏ qua vị trí i)
f(i,j) = f(i-1,j-1) + a[i] (chọn vị trí i làm mở ngoặc)
f(i,j) = f(i-1,j+1) - a[i] (chọn vị trí i làm đóng ngoặc)
Subtask 3: Có \(t \le 1000\) số a khác 0
Nhận thấy chỉ có các số khác 0 mới đóng góp vào tổng, còn các số bằng 0 có thể lựa chọn tùy ý mà không làm thay đổi kết quả. Tìm cách giữ lại vừa đủ các số 0. Một cách thu gọn mảng a: Giữ lại tối đa \(t + t\) số 0 đứng trước và sau toàn bộ số khác 0, và 2 số 0 nằm bên cạnh mỗi một trong \(t\) số khác 0. Như vậy ta đã giữ lại không quá \(5 * t\) số, kích thước đủ nhỏ để thực hiện QHĐ như subtask 2.
Subtask 4:
Dùng tham lam để giải. Khi duyệt tới vị trí nào, ta luôn đảm bảo biểu thức ngoặc hiện tại là biểu thức ngoặc đúng. Giả sử đang duyệt tới \(i\), chọn ngay \(i\) làm đóng ngoặc. Như vậy để biểu thức ngoặc đúng thì cần phải chọn một vị trí \(j \le i\):
- Nếu \(j\) là đóng ngoặc thì chuyển thành bỏ qua \(j\)
- Nếu \(j\) đang không được dùng thì chuyển \(j\) thành mở ngoặc
Nhận thấy là cả 2 lựa chọn đều làm tăng tổng của biểu thức lên một lượng là \(a[j]\). Có thể dùng CTDL priority_queue để nhanh chóng lấy ra \(a[j]\) lớn nhất.
Source code:
// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int INF = 1e9;
int num_elems;
int val[MAX_N];
priority_queue<int, vector<int>, greater<int>> open, close;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
cin >> num_elems;
for (int i = 1; i <= num_elems; i++)
{
cin >> val[i];
}
long long ans = 0;
for (int i = num_elems; i > 0; i--)
{
int a = val[i];
int b = open.empty() ? INF : open.top();
int c = close.empty() ? INF : close.top();
if (a > c)
{
if (c >= b)
{
ans += a - b;
open.pop();
open.push(a);
close.push(b);
}
else
{
ans += a - c;
close.pop();
open.push(a);
}
}
else
{
if (a > b)
{
ans += a - b;
open.pop();
open.push(a);
close.push(b);
}
else
{
close.push(a);
}
}
}
cout << ans;
return 0;
}
Bình luận