VOBRACK - Dãy ngoặc
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Ngoài việc chơi với các bảng số 01, Bé còn rất thích chơi với những dãy ngoặc. Hôm nay, mẹ cho Bé N dãy ngoặc. Bé muốn tạo được một dãy ngoặc đúng bằng việc nối một số dãy ngoặc lại với nhau. Bạn hãy giúp bé nhé.
Một dãy ngoặc đúng được định nghĩa theo kiểu đệ quy như sau:
- Dãy rỗng - dãy không gồm ký tự nào - là dãy ngoặc đúng.
- Nếu X là một dãy ngoặc đúng, thì (X) cũng là một dãy ngoặc đúng. Ví dụ, vì X = ()() là một dãy ngoặc đúng nên (()()) cũng là một dãy ngoặc đúng.
- Nếu X và Y là hai dãy ngoặc đúng, thì XY là một dãy ngoặc đúng. Ví dụ, vì X = (()) và Y = () là các dãy ngoặc đúng, nên XY = (())() cũng là dãy ngoặc đúng.
Một số ví dụ về các dãy không phải là dãy ngoặc đúng: )(, (())), ((()...
Input
- Dòng 1: Số nguyên dương N duy nhất
- N dòng tiếp, mỗi dòng ghi 1 dãy ngoặc
Output
Độ dài của dãy ngoặc lớn nhất tìm được
Chấm điểm
- Trong quá trình thi, bài của bạn sẽ chỉ được chấm với một test duy nhất là test đề bài.
Giới hạn
- Trong tất cả các test, N ≤ 1000, tổng độ dài các dãy ngoặc trong input không quá 10,000
- Trong 30% test, N ≤ 8, tổng độ dài các dãy ngoặc không quá 100.
Example
Input: 3 ( ) )( Output: 4
Giải thích
Bé có thể nối dãy ngoặc thứ 1 với thứ 2 tạo thành dãy ngoặc () là dãy ngoặc đúng. Bé cũng có thể nối dãy ngoặc thứ 1, thứ 3 rồi thứ 2, tạo thành dãy ngoặc ()() là dãy ngoặc đúng.
- Người up: voj
- Nguồn bài: VNOI Online 14