fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> ii;
  6.  
  7. const int INF = 1e9;
  8. const ll LINF = 1e18;
  9.  
  10. template<typename T>
  11. void maximize(T& a, const T& b) {
  12. if (a < b) a = b;
  13. }
  14.  
  15. const int N = 1e6 + 5;
  16.  
  17. // Đây cũng là một dạng dp liên quan đến stack hay gặp
  18. // Nên làm qua trước bài kiểm tra dãy ngoặc đúng bằng stack
  19. // Với mỗi ngoặc đóng s[i] ta cần biết open_pos[i] là vị trí của ngoặc mở tương ứng với s[i]
  20. // mỗi ngoặc đóng s[i] chỉ xác định được duy nhất một open_pos[i], hoặc -1 nếu không tồn tại ngoặc mở tương ứng
  21. // Nhận xét quan trọng: Xâu con s[open_pos[i]..i] là một dãy ngoặc đúng
  22. int n;
  23. string s;
  24. int open_pos[N]; // open_pos[i] = Vị trí của ngoặc mở tương ứng với ngoặc đóng s[i]
  25. int dp[N]; // dp[i] = Độ dài xâu con liên tiếp dài nhất kết thúc tại i thoả mãn là dãy ngoặc đúng
  26.  
  27. int main() {
  28. ios::sync_with_stdio(0); cin.tie(0);
  29. cin >> s;
  30. n = s.size();
  31. s = ' ' + s;
  32.  
  33. memset(open_pos, -1, sizeof open_pos);
  34.  
  35. vector<int> st;
  36. for (int i = 1; i <= n; i++) {
  37. if (s[i] == '(') {
  38. st.push_back(i);
  39. }
  40. else { // s[i] == ')'
  41. if (!st.empty()) {
  42. open_pos[i] = st.back();
  43. st.pop_back();
  44. }
  45. }
  46. }
  47.  
  48. int mx_length = 0;
  49. for (int i = 1; i <= n; i++) {
  50. if (open_pos[i] == -1) continue;
  51. dp[i] = (i - open_pos[i] + 1) + dp[open_pos[i] - 1];
  52. maximize(mx_length, dp[i]);
  53. }
  54.  
  55. int cnt = 0;
  56. for (int i = 1; i <= n; i++) {
  57. cnt += (dp[i] == mx_length);
  58. }
  59. if (mx_length == 0) cnt = 1;
  60.  
  61. cout << mx_length << ' ' << cnt << '\n';
  62. }
Success #stdin #stdout 0.01s 7928KB
stdin
)((())))(()())
stdout
6 2