PTIT027 - Dãy ngoặc đúng dài nhất
Xem dạng PDF
Một nhà toán học và một nhà văn bị một bộ tộc da đỏ bắt. Tù trưởng của bộ lạc này là một người rất thông minh và cũng đã từng được học hành. Sau khi bỏ đói ba ngày, tù trưởng cho lính dắt nhà Toán học vào một căn phòng và bảo ông ta sắp được ăn. Nhà Toán học được đặt ngồi trên một chiếc ghế ở góc phòng, bụng khấp khởi mừng khi nhìn thấy một mâm sơn hào hải vị đặt ở góc phòng bên kia. Tên tù trưởng giải thích:
- Mày phải ngồi yên trên ghế, cứ 1 phút mày lại được quyền kéo cái ghế 1 nửa quãng đường tới mâm cơm.
Nhà Toán học giãy nảy:
- Tao sẽ không tham. Trò giễu cợt này, không một thằng nào là không biết rằng tao sẽ chẳng bao giờ đến được chỗ mâm cơm.
Tù trưởng cũng không làm khó dễ gì nhà Toán học, ông này cắp bụng đói về phòng nhốt mình.Tới lượt nhà Văn học được đưa ra với điều kiện tương tự. Khi nghe tên tù trưởng giải thích luật chơi, mắt ông này sáng rực và ngồi ngay vào ghế. Tù trưởng vờ ngạc nhiên hỏi
- Chẳng nhẽ mày không thấy là mày sẽ chẳng bao giờ đến tới chỗ mâm cơm hay sao?
Nhà văn học mỉm cười:
- Tao không tới tận chỗ mâm cơm, nhưng tao có thể đến … đủ gần để ăn được cơm.
Vì vậy mà nhà văn có thể ăn được cơm và xin Tù trưởng cho nhà toán học cũng được ăn giống mình nhưng muốn được vậy thì phải giải được vấn đề được đưa ra của Tù trưởng đó là:
Cho một xâu chỉ gồm các kí tự '(' và ')'. Một dãy ngoặc đúng được định nghĩa như sau:
- Xâu rỗng là 1 dãy ngoặc đúng.
- Nếu A là 1 dãy ngoặc đúng thì (A) là 1 dãy ngoặc đúng.
- Nếu A và B là 2 dãy ngoặc đúng thì AB là 1 dãy ngoặc đúng.
Cho một xâu S. Nhiệm vụ của bạn là hãy tìm dãy ngoặc đúng dài nhất xuất hiện trong xâu đã cho.
Input
- Dòng đầu tiên là số lượng bộ test T (T ≤ 20).
- Mỗi test gồm một xâu S có độ dài không vượt quá ~10^5~ kí tự.
Output
Với mỗi test in ra một số nguyên là độ dài dãy ngoặc đúng dài nhất tìm được.
Sample
Input #1
3
((()
)()())
()(()))))
Output #1
2
4
6
Problem source: CLB Lập Trình PTIT
Bình luận
include <iostream>
include <stack>
include <string>
include <algorithm>
using namespace std;
int sex(string a) { stack<int> b; b.push(-1); int c = 0; for (int d = 0; d < a.length(); ++d) { if (a[d] == '(') { b.push(d); } else { b.pop(); if (b.empty()) { b.push(d); } else { c = max(c, d - b.top()); } } } return c; }
int main() { int e; cin >> e; while (e--) { string f; cin >> f; cout << sex(f) << endl; } return 0; }
tên hàm nghe cay v : )