fork(3) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> countPrefixLen(const vector<string>& words) {
  9. 	int n = words.size();
  10. 	vector<int> prefixLen(n+1);
  11. 	for (int i = 1; i <= n; ++i) {
  12. 		prefixLen[i] = prefixLen[i-1] + words[i-1].length();
  13. 	} 
  14. 	return prefixLen;
  15. }
  16.  
  17. void output(int answer, const vector<int>& best, const vector<string>& words) {
  18. 	cout << answer << endl;
  19.  
  20. 	int j = best.size()-1;
  21. 	vector<int> restoreIndex(1, j);
  22. 	while (j > 0) {
  23. 		int i = best[j];
  24. 		restoreIndex.push_back(i);
  25. 		j = i;
  26. 	}
  27. 	reverse(restoreIndex.begin(), restoreIndex.end());
  28. 	for (int i = 0; i+1 < restoreIndex.size(); ++i) {
  29. 		for (int j = restoreIndex[i]; j < restoreIndex[i+1]; ++j) {
  30. 			cout << words[j] << ' ';
  31. 		}
  32. 		cout << endl;
  33. 	}
  34.  
  35. }
  36.  
  37. int main() {
  38. 	const vector<string> words = {"would", "a", "cat", "eat", "a", "mouse"};
  39. 	const int L = 5;
  40. 	int n = words.size();
  41.  
  42. 	vector<int> prefixLen = countPrefixLen(words);
  43.  
  44. 	vector<int> f(n+1);
  45. 	vector<int> best(n+1, -1);
  46. 	int maxL = prefixLen[n];
  47. 	f[0] = 0;
  48.  
  49. 	for (int i = 1; i <= n; ++i) {
  50. 		f[i] = maxL; 
  51. 		for (int j = 0; j < i; ++j) {
  52. 			int totalLen = prefixLen[i] - prefixLen[j];
  53. 			if (totalLen >= L) {
  54. 				int maxLen = max(f[j], totalLen);
  55. 				if (f[i] > maxLen) {
  56. 					f[i] = maxLen;
  57. 					best[i] = j;
  58. 				}
  59. 			}
  60. 		} 
  61. 	}
  62.  
  63. 	output(f[n], best, words);	
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
6
would a 
cat eat 
a mouse
https://ideone.com/AaV5C8
language:
C++ (gcc 8.3)
created:
6 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!