fork download
copy 
  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. // - Từ thuật trâu O(q * n^2), ta thấy rằng bản chất của 2 vòng for là đang đi tính tổng của hình chữ nhật (l, l, r, r) của bảng dp
  12. // - Do đó, ta có thể tối ưu theo 2 hướng như sau:
  13. // * Hướng tối ưu 1: Prefix Sum 2D: 
  14. // - Ta có thể chuẩn bị trước mảng prefix sum 2D sum[x][y] của bảng dp trong O(n^2) và trả lời mỗi truy vấn tính tổng hình chữ nhật trong O(1)
  15. // * Hướng tối ưu 2: DP Range:
  16. // - Gọi ans[l][r] = Đáp án của đoạn [l, r] = Tổng của hình chữ nhật (l, l, r, r)
  17. // - Ta có công thức như sau: ans[l][r] = ans[l + 1][r] + ans[l][r - 1] - ans[l + 1][r - 1] + (đóng góp của cặp (l, r))   
  18. const int N = 5e3 + 5; 
  19.  
  20. int n, q;  
  21. string s;  
  22.  
  23. bool dp[N][N]; // dp[l][r] = true/false = Xâu con s[l..r] có phải là xâu đối xứng hay không
  24. int ans[N][N]; // ans[l][r] = Đáp án của đoạn [l, r]
  25.  
  26. int main() {
  27. 	ios::sync_with_stdio(false); 
  28. 	cin.tie(nullptr); 	
  29. 	cin >> s >> q; 
  30. 	n = s.size();  
  31. 	s = ' ' + s;  
  32.  
  33. 	for (int l = n; l >= 1; l--) {
  34. 		for (int r = l; r <= n; r++) {
  35. 			if (l == r) {
  36. 				dp[l][r] = 1;  
  37. 				continue; 
  38. 			}
  39. 			if (l + 1 == r) {
  40. 				dp[l][r] = (s[l] == s[r]); 
  41. 				continue; 
  42. 			}
  43. 			dp[l][r] = (s[l] == s[r]) & (dp[l + 1][r - 1]); 
  44. 		}
  45. 	}
  46.  
  47. 	for (int l = n; l >= 1; l--) {
  48. 		for (int r = l; r <= n; r++) {
  49. 			ans[l][r] = ans[l + 1][r] + ans[l][r - 1] - ans[l + 1][r - 1] + dp[l][r]; 
  50. 		}
  51. 	}
  52.  
  53. 	while (q--) {
  54. 		int l, r; 
  55. 		cin >> l >> r;
  56. 		cout << ans[l][r] << '\n'; 
  57. 	}
  58. }
Success #stdin #stdout 0.01s 5692KB
comments (?)
stdin
copy 
caaaba
5
1 1
1 4
2 3
4 6
4 5
stdout
copy 
1
7
3
4
2
https://ideone.com/htI49S
language:
C++14 (gcc 8.3)
created:
19 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!