#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 8;
int D[] = { 0, 90, 100, 180, 270, 280, 300, 380 };
int C[] = { 3, 7, 2, 1, 3, 5, 10, 4 };
int targetDist = 400;
int range = 100;
int bestcost[1000000], opt[1000000];
int main() {
bestcost[0] = C[0];
for (int i = 1; i < n; ++i) {
bestcost[i] = 1<<30;
for (int j = 0; j < i; ++j) {
int xx = bestcost[j] + C[i];
if (D[i] - D[j] <= range && xx < bestcost[i]) {
bestcost[i] = xx;
opt[i] = j;
}
}
}
int ans = 1<<30;
int last = -1;
for (int i = 0; i < n; ++i)
if (targetDist - D[i] <= range && bestcost[i] < ans) {
ans = bestcost[i];
last = i;
}
cout << "optimal cost to get to target at " << targetDist << " = " << ans << endl;
vector<int> res;
while (last != 0) res.push_back(last), last = opt[last];
res.push_back(0);
reverse(begin(res), end(res));
cout << "optimal path = ";
for (int x: res) cout << x << " "; cout << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG4gPSA4OwppbnQgRFtdID0geyAwLCA5MCwgMTAwLCAxODAsIDI3MCwgMjgwLCAzMDAsIDM4MCB9OwppbnQgQ1tdID0geyAzLCA3LCAyLCAxLCAzLCA1LCAxMCwgNCB9OwppbnQgdGFyZ2V0RGlzdCA9IDQwMDsKaW50IHJhbmdlID0gMTAwOwoKaW50IGJlc3Rjb3N0WzEwMDAwMDBdLCBvcHRbMTAwMDAwMF07CmludCBtYWluKCkgewogIGJlc3Rjb3N0WzBdID0gQ1swXTsKICBmb3IgKGludCBpID0gMTsgaSA8IG47ICsraSkgewogICAgYmVzdGNvc3RbaV0gPSAxPDwzMDsKICAgIGZvciAoaW50IGogPSAwOyBqIDwgaTsgKytqKSB7CiAgICAgIGludCB4eCA9IGJlc3Rjb3N0W2pdICsgQ1tpXTsKICAgICAgaWYgKERbaV0gLSBEW2pdIDw9IHJhbmdlICYmIHh4IDwgYmVzdGNvc3RbaV0pIHsKICAgICAgICBiZXN0Y29zdFtpXSA9IHh4OwogICAgICAgIG9wdFtpXSA9IGo7CiAgICAgIH0KICAgIH0KICB9CiAgaW50IGFucyA9IDE8PDMwOwogIGludCBsYXN0ID0gLTE7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpCiAgICBpZiAodGFyZ2V0RGlzdCAtIERbaV0gPD0gcmFuZ2UgJiYgYmVzdGNvc3RbaV0gPCBhbnMpIHsKICAgICAgYW5zID0gYmVzdGNvc3RbaV07CiAgICAgIGxhc3QgPSBpOwogICAgfQogIGNvdXQgPDwgIm9wdGltYWwgY29zdCB0byBnZXQgdG8gdGFyZ2V0IGF0ICIgPDwgdGFyZ2V0RGlzdCA8PCAiID0gIiA8PCBhbnMgPDwgZW5kbDsKICB2ZWN0b3I8aW50PiByZXM7CiAgd2hpbGUgKGxhc3QgIT0gMCkgcmVzLnB1c2hfYmFjayhsYXN0KSwgbGFzdCA9IG9wdFtsYXN0XTsKICByZXMucHVzaF9iYWNrKDApOwogIHJldmVyc2UoYmVnaW4ocmVzKSwgZW5kKHJlcykpOwogIGNvdXQgPDwgIm9wdGltYWwgcGF0aCA9ICI7CiAgZm9yIChpbnQgeDogcmVzKSBjb3V0IDw8IHggPDwgIiAiOyBjb3V0IDw8IGVuZGw7Cn0=