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. const int N = 3e5 + 5; 
  12.  
  13. // Đối với các bài dp liên quan đến stack thì đây là một dạng hay gặp
  14. // Như trong bài này hoặc những bài tương tự thì công thức dp sẽ có dạng dp[i] = min/max{dp[j] + min/max{a[j + 1...i]}} với j < i 
  15. // Hay tóm lại là trong công thức dp có đề cập đến min/max của một đoạn
  16. // Để tính được dp[i] thì ta xét 2 trường hợp như sau:
  17. // Trường hợp 1: a[i] đóng vai trò là min (trường hợp a[i] đóng vai trò là max cũng tương tự):
  18. // - Nhận xét: Gọi l[i] = Phần tử gần nhất bên trái < a[i]
  19. //             => a[i] sẽ đóng vai trò là min trong đoạn [j + 1, i] với l[i] <= j < i
  20. // => dp[i] = min/max{dp[j]} + a[i] (với l[i] <= j < i)
  21. // => Có thể tối ưu bằng Segment Tree
  22. // Trường hợp 2: a[i] không đóng vai trò là min
  23. // Có thể thấy rằng với j < l[i] thì a[i] không còn đóng vai trò là min trong đoạn [j + 1, i] nữa
  24. // Ở đây có thể một số em nghĩ rằng sẽ phải xét rất nhiều trường hợp nhưng mọi thứ đơn giản chỉ là truy hồi về dp[l[i]]
  25. // Có thể giải thích đơn giản là khi truy hồi về dp[l[i]] thì nó cũng sẽ xét qua trường hợp 1 là a[l[i]] đóng vai trò là min,
  26. // còn trường hợp 2 a[l[i]] không đóng vai trò là min thì sẽ tiếp tục truy hồi về dp[l[l[i]]],... và cứ thế một cách "đệ quy" 
  27. int n; 
  28. int h[N]; 
  29. int b[N]; 
  30.  
  31. ll seg[4 * N]; // seg[id] = max{dp[l..r]} do nút id quản lí
  32.  
  33. void update(int id, int l, int r, int pos, ll val) {
  34. 	if (l > pos || r < pos) return; 
  35.  
  36. 	if (l == r) {
  37. 		seg[id] = val; 
  38. 		return; 
  39. 	}
  40.  
  41. 	int mid = (l + r) >> 1; 
  42. 	update(id * 2, l, mid, pos, val); 
  43. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  44.  
  45. 	seg[id] = max(seg[id * 2], seg[id * 2 + 1]); 
  46. }
  47.  
  48. ll getMax(int id, int l, int r, int u, int v) {
  49. 	if (l > v || r < u) return -LINF; 
  50.  
  51. 	if (u <= l && r <= v) return seg[id]; 
  52.  
  53. 	int mid = (l + r) >> 1; 
  54. 	return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v)); 
  55. }
  56.  
  57. int l[N]; // l[i] = phần tử gần nhất bên trái < h[i]	
  58. ll dp[N]; // dp[i] = Đáp án tối ưu khi xét các toà nhà từ 1 đến i 
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(false); 
  62. 	cin.tie(nullptr); 	
  63. 	cin >> n; 
  64. 	for (int i = 1; i <= n; i++) cin >> h[i]; 	
  65. 	for (int i = 1; i <= n; i++) cin >> b[i]; 
  66.  
  67. 	vector<int> st;  
  68. 	for (int i = 1; i <= n; i++) {
  69. 		while (!st.empty() && h[st.back()] >= h[i]) st.pop_back(); 
  70. 		l[i] = st.empty() ? 0 : st.back();  
  71. 		st.push_back(i); 
  72. 	}
  73.  
  74. 	dp[0] = 0;   
  75. 	update(1, 0, n, 0, dp[0]); 
  76.  
  77. 	for (int i = 1; i <= n; i++) {
  78. 		dp[i] = getMax(1, 0, n, l[i], i - 1) + b[i]; // Trường hợp 1
  79. 		if (l[i] > 0) dp[i] = max(dp[i], dp[l[i]]); // Trường hợp 2
  80. 		update(1, 0, n, i, dp[i]); 
  81. 	}
  82.  
  83. 	cout << dp[n] << '\n'; 
  84. }
Success #stdin #stdout 0.01s 7564KB
comments (?)
stdin
copy 
5
1 2 3 5 4
1 5 3 2 4
stdout
copy 
15
https://ideone.com/I5pemu
language:
C++14 (gcc 8.3)
created:
240 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!