fork(5) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int n = 8;
  7. int D[] = { 0, 90, 100, 180, 270, 280, 300, 380 };
  8. int C[] = { 3, 7, 2, 1, 3, 5, 10, 4 };
  9. int targetDist = 400;
  10. int range = 100;
  11.  
  12. int bestcost[1000000], opt[1000000];
  13. int main() {
  14.   bestcost[0] = C[0];
  15.   for (int i = 1; i < n; ++i) {
  16.     bestcost[i] = 1<<30;
  17.     for (int j = 0; j < i; ++j) {
  18.       int xx = bestcost[j] + C[i];
  19.       if (D[i] - D[j] <= range && xx < bestcost[i]) {
  20.         bestcost[i] = xx;
  21.         opt[i] = j;
  22.       }
  23.     }
  24.   }
  25.   int ans = 1<<30;
  26.   int last = -1;
  27.   for (int i = 0; i < n; ++i)
  28.     if (targetDist - D[i] <= range && bestcost[i] < ans) {
  29.       ans = bestcost[i];
  30.       last = i;
  31.     }
  32.   cout << "optimal cost to get to target at " << targetDist << " = " << ans << endl;
  33.   vector<int> res;
  34.   while (last != 0) res.push_back(last), last = opt[last];
  35.   res.push_back(0);
  36.   reverse(begin(res), end(res));
  37.   cout << "optimal path = ";
  38.   for (int x: res) cout << x << " "; cout << endl;
  39. }
Success #stdin #stdout 0s 11240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
optimal cost to get to target at 400 = 15
optimal path = 0 2 3 5 7
https://ideone.com/gm5eit
language:
C++14 (gcc 8.3)
created:
10 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!