fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <iterator>
  5. #include <string>
  6. #include <sstream>
  7. //#include "sequence_lister.h"
  8.  
  9. using namespace std;
  10.  
  11. #define INF 1000000000
  12.  
  13. class MaxMinGap {
  14.     vector<int> x;
  15. 	int M;
  16. 	const int N;		// Just for convenience -- it's just x.size()
  17. 	vector<vector<int> > fMemo;
  18. 	vector<vector<int> > pred;		// Stores d values, from which the right i and j can be computed
  19. 	int bestM;
  20.  
  21. 	// The following version finds solutions having *exactly* the given number of deletions,
  22. 	// which is what we need to get the right answer.
  23. 	int f(int i, int j) {
  24. 		if (i == N - 1) {
  25. 			if (j > 0) {
  26. 				return 0;		// The deletions won't all fit
  27. 			} else {
  28. 				return INF;
  29. 			}
  30. 		}
  31.  
  32. 		if (fMemo[i][j] == -1) {
  33. 			int best = -1;
  34. 			int bestD = -1;
  35. 			for (int d = 0; d <= min(j, N - i - 2); ++d) {
  36. 				int guess = min(x[i + d + 1] - x[i], f(i + d + 1, j - d));
  37. 				if (guess > best) {
  38. 					best = guess;
  39. 					bestD = d;
  40. 				}
  41. 			}
  42.  
  43. 			fMemo[i][j] = best;
  44. 			pred[i][j] = bestD;
  45. 		}
  46.  
  47. 		return fMemo[i][j];
  48. 	}
  49.  
  50. public:
  51. 	MaxMinGap(vector<int> x, int M) : x(x), M(M), N(x.size()), fMemo(x.size() + 1, vector<int>(M + 1, -1)), pred(x.size() + 1, vector<int>(M + 1, -1)), bestM(INF) {
  52. 		solve();		// Might as well do it right away
  53. 	}
  54.  
  55. 	// Must be called before getSolution() or getBestMinGapSize()
  56. 	void solve() {
  57. 		int best;
  58. 		for (int i = M; i >= 0; --i) {
  59. 			int guess = f(0, i);
  60. 			if (i < M && guess < best) {
  61. 				break;
  62. 			}
  63.  
  64. 			best = guess;
  65. 			bestM = i;
  66. 		}
  67. 	}
  68.  
  69. 	// The following version doesn't find the solution having the minimum number of deletions!
  70. 	//int f(int i, int j) {
  71. 	//	if (i == N - 1) {
  72. 	//		return INF;
  73. 	//	}
  74. 	//	
  75. 	//	if (fMemo[i][j] == -1) {
  76. 	//		int best = -1;
  77. 	//		int bestD = -1;
  78. 	//		for (int d = 0; d <= min(j, N - i - 2); ++d) {
  79. 	//			int guess = min(x[i + d + 1] - x[i], f(i + d + 1, j - d));
  80. 	//			if (guess > best) {
  81. 	//				best = guess;
  82. 	//				bestD = d;
  83. 	//			}
  84. 	//		}
  85. 	//		
  86. 	//		fMemo[i][j] = best;
  87. 	//		pred[i][j] = bestD;
  88. 	//	}
  89. 	//	
  90. 	//	return fMemo[i][j];
  91. 	//}
  92.  
  93. 	// Wrongheaded!  Lacks optimal substructure on close inspection.
  94. 	//// The second element is the number of deletions that weren't needed, so
  95. 	//// that comparisons can be done with a simple ">".
  96. 	//pair<int, int> f(int i, int j) {
  97. 	//	if (i == N - 1) {
  98. 	//		return make_pair(INF, j);
  99. 	//	}
  100. 	//	
  101. 	//	if (fMemo[i][j].first == -1) {
  102. 	//		pair<int, int> best = make_pair(-1, -1);
  103. 	//		int bestD = -1;
  104. 	//		for (int d = 0; d <= min(j, N - i - 2); ++d) {
  105. 	//			pair<int, int> subproblem = f(i + d + 1, j - d);
  106. 	//			pair<int, int> guess;
  107. 	//			guess.first = min(x[i + d + 1] - x[i], subproblem.first);
  108. 	//			guess.second = subproblem.second;
  109. 	//			if (guess > best) {
  110. 	//				best = guess;
  111. 	//				bestD = d;
  112. 	//			}
  113. 	//		}
  114. 	//		
  115. 	//		fMemo[i][j] = best;
  116. 	//		pred[i][j] = bestD;
  117. 	//	}
  118. 	//	
  119. 	//	return fMemo[i][j];
  120. 	//}
  121.  
  122. 	// solve() must be run first.
  123. 	int getBestMinGapSize() {
  124. 		return f(0, bestM);
  125. 	}
  126.  
  127. 	// solve() must be run first.
  128. 	int getFewestDeletions() {
  129. 		return bestM;
  130. 	}
  131.  
  132. 	// solve() must be run first.
  133. 	vector<int> getSolution() {
  134. 		vector<int> numbers;
  135.  
  136. 		int i = 0, j = bestM;
  137. 		while (pred[i][j] != -1) {
  138. 			numbers.push_back(x[i]);
  139. 			int d = pred[i][j];
  140. 			i += d + 1;
  141. 			j -= d;
  142. 		}
  143.  
  144. 		numbers.push_back(x[N - 1]);
  145. 		return numbers;
  146. 	}
  147. };
  148.  
  149. // Function template for joining sequences into strings
  150. template <typename C>
  151. string list_sequence(C c, string delim) {
  152. 	ostringstream oss;
  153. 	for (typename C::const_iterator i(c.begin()); i != c.end(); ++i) {
  154. 		if (i != c.begin()) {
  155. 			oss << delim;
  156. 		}
  157.  
  158. 		oss << *i;
  159. 	}
  160.  
  161. 	return oss.str();
  162. }
  163.  
  164. int main(int argc, char **argv) {
  165. 	cout << "Enter M (maximum number of numbers to delete): ";
  166. 	int M;
  167. 	cin >> M;
  168. 	cout << "\nEnter numbers (Ctrl-Z to end): ";
  169. 	MaxMinGap mmg(vector<int>(istream_iterator<int>(cin), istream_iterator<int>()), M);
  170. 	cout << "\nBest solution has a minimum gap size of " << mmg.getBestMinGapSize() << ", with " << mmg.getFewestDeletions() << " deletions needed.\n";
  171. 	cout << "Example optimal solution: " << list_sequence(mmg.getSolution(), " ") << ".\n";
  172.  
  173. 	return 0;
  174. }
  175.  
Success #stdin #stdout 0s 3044KB
comments (?)
stdin
copy 
7
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100
stdout
copy 
Enter M (maximum number of numbers to delete): 
Enter numbers (Ctrl-Z to end): 
Best solution has a minimum gap size of 5, with 6 deletions needed.
Example optimal solution: 0 7 15 26 31 38 44 53 60 73 80 88 93 100.
https://ideone.com/PKfhDv
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!