fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, k;
  5. int pos[202];
  6. int memo[202][33];
  7. int callback[202][33];
  8.  
  9. int dp(int rest, int depot) {
  10. 	if(rest == n && depot == k) return 0;
  11. 	if(rest == n || depot == k) return 1e9;
  12. 	if(memo[rest][depot] != -1) return memo[rest][depot];
  13. 	int ans = 1e9, dist = 0;
  14. 	for(int i = rest; i < n; i++) {
  15. 		int mid = (i+rest)/2;
  16. 		dist += pos[i]-pos[mid];
  17. 		int next = dp(i+1, depot+1)+dist;
  18. 		if(ans > next) {
  19. 			ans = next;
  20. 			callback[rest][depot] = i+1;
  21. 		}
  22. 	}
  23. 	return memo[rest][depot] = ans;
  24. }
  25.  
  26. void trace(int rest, int depot, int depth = 1) {
  27. 	if(rest == n && depot == k) return;
  28. 	int track = callback[rest][depot];
  29. 	cout << "Depot " << depth << " at restaurant " <<
  30. 		(rest+track-1)/2+1 << " serves restaurant";
  31. 	if(rest != track-1)
  32. 		cout << "s " << rest+1 << " to " << track << endl;
  33. 	else
  34. 		cout << " " << rest+1 << endl;
  35. 	trace(track, depot+1, depth+1);
  36. }
  37.  
  38. int main() {
  39. 	int tc = 1;
  40. 	while(cin >> n >> k && n > 0 && k > 0) {
  41. 		for(int i = 0; i < n; i++)
  42. 			cin >> pos[i];
  43. 		memset(memo, -1, sizeof(memo));
  44. 		cout << "Chain " << tc++ << endl;
  45. 		int ans = dp(0, 0);
  46. 		trace(0, 0);
  47. 		cout << "Total distance sum = " << ans << endl << endl;
  48. 	}
  49. 	return 0;
  50. }
  51.  
  52. /*
  53.  5
  54.  0
  55.  5  6
  56.  0  1
  57.  5  6 12
  58.  1  0  6			= 7
  59.  5  6 12 19
  60.  1  0  6 13			= 20 = 7+13
  61.  5  6 12 19 20
  62.  7  6  0  7  8		= 28 = 20+8
  63.  5  6 12 19 20 27
  64.  7  6  0  7  8 15
  65. */
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
6 3
5 6 12 19 20 27
8 3
5 6 7 8 12 19 20 27
0 0
stdout
copy 
Chain 1
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 4 to 5
Depot 3 at restaurant 6 serves restaurant 6
Total distance sum = 8

Chain 2
Depot 1 at restaurant 3 serves restaurants 1 to 5
Depot 2 at restaurant 6 serves restaurants 6 to 7
Depot 3 at restaurant 8 serves restaurant 8
Total distance sum = 10
https://ideone.com/A0JQpO
language:
C++ (gcc 8.3)
created:
328 days 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!