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. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false;  
  15. }
  16.  
  17. const int N = 4e5 + 5;  
  18.  
  19. // Bài toán 1: Chọn các chai rượu sao cho tổng lớn nhất và không được chọn k chai liên tiếp nhau
  20. // Bài toán 2: Chọn bỏ đi các chai rượu sao cho tổng nhỏ nhất và chỉ số của 2 chai liên tiếp được chọn cách nhau không quá k (<= k) 
  21. // *Hướng giải 1: 
  22. // - Bài toán 1 chính là bài toán được phát biểu trong đề bài, vẫn có cách giải bằng dp nhưng công thức dp phức tạp hơn
  23. // - Gọi dp[i] = Tổng lớn nhất của các chai rượu được chọn khi xét đến chai rượu thứ i và thoả mãn điều kiện
  24. // - dp[i] = min{dp[j] + pref[i] - pref[j + 1]} (với j thuộc đoạn [i - k, i - 1])
  25. // - biến đổi lại ta có dp[i] = min{dp[j] - pref[j + 1]} + pref[i]
  26. // - Vậy từ đây với mỗi i ta cần tìm dp[j] - pref[j + 1] nhỏ nhất với j thuộc đoạn [i - k, i - 1]
  27. // => Tối ưu bằng Deque/Segment Tree, độ phức tạp O(n)/O(nlogn), nhưng phần truy vết sẽ hơi vất vả một chút
  28. // *Hướng giải 2:
  29. // - Nhận xét: Từ đáp án có được ở bài toán 2 ta có thể suy ra được đáp án của bài toán 1 (và ngược lại) 
  30. //             Hay nói cách khác thay vì đi tìm các chai rượu được chọn thì ta có thể đi tìm các chai rượu bị bỏ đi 
  31. // - Gọi dp[i] = Tổng nhỏ nhất của các chai rượu được chọn để bỏ đi khi xét đến chai rượu thứ i, thoả mãn điều kiện và chai thứ i chắc chắn được chọn 
  32. // - dp[i] = min{dp[j]} + a[i] (với j thuộc đoạn [i - k, i - 1])
  33. // => Tối ưu bằng Deque/Segment Tree, độ phức tạp O(n)/O(nlogn)
  34. int n, k; 
  35. int a[N]; 
  36. ll dp[N]; 
  37. int p[N]; // p[i] = vị trí của chai rượu trước đó được chọn nếu chọn chai thứ i 
  38.  
  39. bool removed[N]; // removed[i] = 0/1: chai thứ i có được chọn để bỏ đi hay không 
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(false); 
  43. 	cin.tie(nullptr); 	
  44. 	cin >> n >> k; 
  45. 	ll sum = 0; 
  46. 	for (int i = 1; i <= n; i++) {
  47. 		cin >> a[i];  
  48. 		sum += a[i]; 
  49. 	} 
  50.  
  51. 	for (int i = 0; i <= n; i++) dp[i] = LINF;
  52. 	dp[0] = 0;   
  53.  
  54. 	// for (int i = 1; i <= n; i++) {
  55. 	// 	for (int j = max(0, i - k); j <= i - 1; j++) {
  56. 	// 		if (minimize(dp[i], dp[j] + a[i])) {
  57. 	// 			p[i] = j;  
  58. 	// 		}
  59. 	// 	}
  60. 	// } O(n * k)
  61.  
  62. 	deque<int> dq;  
  63. 	for (int i = 1; i <= n; i++) {
  64. 		while (!dq.empty() && dp[dq.back()] > dp[i - 1]) dq.pop_back(); 
  65. 		dq.push_back(i - 1);  
  66. 		if (dq.front() == i - k - 1) dq.pop_front();  
  67. 		dp[i] = dp[dq.front()] + a[i]; 
  68. 		p[i] = dq.front();  
  69. 	} // O(n)
  70.  
  71. 	ll ans = LINF;  
  72. 	int last = 0;   
  73. 	for (int i = max(0, n - k + 1); i <= n; i++) {
  74. 		if (minimize(ans, dp[i])) {
  75. 			last = i;  
  76. 		}
  77. 	}
  78.  
  79. 	int cnt = 0;   
  80. 	while (true) {
  81. 		if (last == 0) break; 
  82. 		removed[last] = true;
  83. 		cnt++;  
  84. 		last = p[last];  
  85. 	}
  86.  
  87. 	cnt = n - cnt;  
  88. 	ans = sum - ans;   
  89.  
  90. 	cout << cnt << ' ' << ans << '\n';   
  91. 	for (int i = 1; i <= n; i++) {
  92. 		if (removed[i]) continue; 
  93. 		cout << i << ' '; 
  94. 	}
  95. }
Success #stdin #stdout 0.01s 7712KB
comments (?)
stdin 
6 3
6 10 10 13 10 10
stdout 
4 40
2 3 5 6
https://ideone.com/gWMq29
language:
C++14 (gcc 8.3)
created:
241 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!