fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 3e3 + 5;  
  12. const int MOD = 998244353; 
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. int n;   
  20. string s;  
  21. int dp[N][N]; // dp[i][d] = Số dãy ngoặc khi xét đến vị trí thứ i 
  22. 			  //            với chênh lệch ngoặc mở - ngoặc đóng là d
  23.  
  24. int main() {
  25. 	ios::sync_with_stdio(false); 
  26. 	cin.tie(nullptr);  	
  27. 	cin >> s; 
  28. 	n = s.size(); 
  29. 	s = ' ' + s;   
  30.  
  31. 	dp[0][0] = 1;   
  32. 	for (int i = 1; i <= n; i++) {
  33. 		for (int prev_d = 0; prev_d <= n; prev_d++) {
  34. 			// chọn ngoặc mở
  35. 			if (s[i] == '?' || s[i] == '(') {
  36. 				add(dp[i][prev_d + 1], dp[i - 1][prev_d]);  
  37. 			}
  38. 			// chọn ngoặc đóng
  39. 			if (s[i] == '?' || s[i] == ')') {
  40. 				if (prev_d > 0) add(dp[i][prev_d - 1], dp[i - 1][prev_d]);  
  41. 			}
  42. 		}
  43. 	}
  44.  
  45. 	cout << dp[n][0] << '\n'; 
  46. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
(???(?
stdout 
2
https://ideone.com/V3oiNV
language:
C++14 (gcc 8.3)
created:
39 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!