fork download
copy 
  1.  
  2. // Problem : 662 - Fast Food
  3. // Contest : UVa Online Judge
  4. // URL : https://o...content-available-to-author-only...e.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=603
  5. // Memory Limit : 32 MB
  6. // Time Limit : 3000 ms
  7. // Powered by CP Editor (https://g...content-available-to-author-only...b.com/cpeditor/cpeditor)
  8.  
  9. #define _CRT_SECURE_NO_WARNINGS
  10. #define _USE_MATH_DEFINES
  11. #include<bits/stdc++.h>
  12. #include<unordered_map>
  13. using namespace std;
  14. #define Ma7moud_7amdy                 \
  15.     ios_base::sync_with_stdio(false); \
  16.     cin.tie(NULL);                    \
  17.     cout.tie(NULL)
  18. #define Open_Sesame Open()
  19. #define all(v) ((v).begin()), ((v).end())
  20. #define allr(v) ((v).rbegin()), ((v).rend())
  21. #define clr(arr, x) memset(arr, x, sizeof arr)
  22. #define endl "\n"
  23. #define watch(x) cout << #x << " = " << x << endl;
  24. #define RT(x) return cout << (x), 0;
  25. #define Accepted 0
  26. #define INF 0x3f3f3f3f3f3f3f3fLL
  27. typedef long long ll;
  28. typedef vector<int> vi;
  29. const int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
  30. const int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
  31. void Open()
  32. {
  33. #ifndef ONLINE_JUDGE 
  34. 	freopen("Input.txt", "r", stdin);
  35. 	freopen("Output.txt", "w", stdout);
  36. #endif
  37. }
  38. const int mod = ll(1e9 + 7), N = 2000 + 5;
  39. //“Nobody but you have to believe in your dreams to make them a reality.” ― Germany Kent
  40. int n, k;
  41. ll mem[201][201][31], vis[201][201][31], T = 0;
  42.  
  43. vector<int>v;
  44. ll solve(int i, int lst, int rem) {
  45. 	if (rem < 0)return 1e17;
  46. 	if (i == n) {
  47. 		return (rem == 0 && lst == i ? 0 : 1e17);
  48. 	}
  49. 	ll& ret = mem[i][lst][rem];
  50. 	if (vis[i][lst][rem] == T)return ret;
  51. 	vis[i][lst][rem] = T;
  52. 	ret = 1e17;
  53. 	ret = min(ret, solve(i + 1, lst, rem));
  54. 	ll mnSum = 1e17;
  55. 	ll curSum = 0;
  56. 	for (int j = lst; j <= i; j++) {
  57. 		curSum += abs(v[j] - v[lst]);
  58. 	}
  59. 	mnSum = min(curSum, mnSum);
  60. 	for (int nxt = lst + 1; nxt <= i; nxt++) {
  61. 		ll curSum = mnSum + 1LL * abs(v[nxt] - v[lst]) * (nxt - lst) - 1LL * abs(v[nxt] - v[lst]) * (i - nxt + 1);
  62. 		mnSum = min(curSum, mnSum);
  63. 	}
  64.  
  65.  
  66. 	ret = min(ret, solve(i + 1, i + 1, rem - 1) + mnSum);
  67. 	return ret;
  68. }
  69. int dCur = 0;
  70. void build(int i, int lst, int rem) {
  71. 	if (rem < 0)return;
  72. 	if (i == n) {
  73. 		return;
  74. 	}
  75. 	ll ret = mem[i][lst][rem];
  76. 	if (ret == solve(i + 1, lst, rem))return build(i + 1, lst, rem);
  77. 	ll mnSum = 1e17;
  78. 	ll curSum = 0;
  79. 	for (int j = lst; j <= i; j++) {
  80. 		curSum += abs(v[j] - v[lst]);
  81. 	}
  82. 	mnSum = min(curSum, mnSum);
  83. 	int idx = lst + 1;
  84. 	for (int nxt = lst + 1; nxt <= i; nxt++) {
  85. 		ll curSum = mnSum + 1LL * abs(v[nxt] - v[lst]) * (nxt - lst) - 1LL * abs(v[nxt] - v[lst]) * (i - nxt + 1);
  86. 		mnSum = min(curSum, mnSum);
  87. 		if (mnSum == curSum)idx = nxt + 1;
  88. 	}
  89. 	if (ret == solve(i + 1, i + 1, rem - 1) + mnSum) {
  90. 		cout << "Depot " << ++dCur << " at restaurant " << idx;
  91. 		if (lst != i)
  92. 			cout << " serves restaurants " << lst + 1 << " to " << i + 1 << endl;
  93. 		else
  94. 			cout << " serves restaurant " << lst + 1 << endl;
  95. 		build(i + 1, i + 1, rem - 1);
  96. 	}
  97. 	return;
  98. }
  99.  
  100. int main()
  101. {
  102. 	Ma7moud_7amdy;
  103. 	Open_Sesame;
  104.  
  105. 	while (cin >> n >> k && n && ++T) {
  106. 		dCur = 0;;
  107. 		v = vector<int>(n);
  108. 		for (int i = 0; i < n; i++) {
  109. 			cin >> v[i];
  110. 		}
  111.  
  112. 		ll ans = solve(0, 0, k);
  113. 		cout << "Chain " << T << endl;
  114. 		build(0, 0, k);
  115. 		cout << "Total distance sum = " << ans << endl;
  116. 		cout << endl;
  117. 	}
  118. }
Success #stdin #stdout 0s 4436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uatWtc
language:
C++14 (gcc 8.3)
created:
3 years 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!