C/C++

Помогите решить задачу на c++

Помогите решить задачу
вообще не понимаю как подступиться
Предлагаю вариант решения через динамическое программирование.
В массиве len_a на i-м месте будем хранить длину куска дороги A от (i-1)-й до i-й развилки (нулевая развилка это R).
В массиве len_b на i-м месте будем хранить длину куска дороги B от (i-1)-й до i-й развилки.
В массиве min_len_a на i-м месте хранить минимальную длину пути между началом дорог R и точкой, где на дороге A начинается i-я по счету развилка.
В массиве min_len_b на i-м месте хранить минимальную длину пути между началом дорог R и точкой, где на дороге B начинается i-я по счету развилка.
В массиве road_connector на i-м месте будем хранить длину i-й по счету связки.

Основная идея. Для любой развилки на дороге A существует всего 2 варианта, как можно добраться до нее
1) от предыдущей развилки на дороге А, продолжая ехать по дороге А (зеленый маршрут на рисунке)
2) от предыдущей развилки на дороге В, проехав по дороге B до текущей развилки и переехав соединительную дорогу (красный маршрут на рисунке)
Из этих вариантов нужно выбрать минимальный. Это отражено в данной строке:
min_len_a[i] = min(min_len_a[i-1] + len_a[i], min_len_b[i-1] + len_b[i] + road_connector[i]);
Аналогично для дороги B.

https://www.codepile.net/pile/vxZjmrxl

#include iostream
using namespace std;
int main() {
int n;
cin >> n;
int len_a[n], len_b[n], road_connector[n];
for (int i = 1; i <= n; i ++) {
cin >> len_a[i] >> len_b[i] >> road_connector[i];
}
int min_len_a[n], min_len_b[n];
min_len_a[1] = min(len_a[1], len_b[1] + road_connector[1]);
min_len_b[1] = min(len_b[1], len_a[1] + road_connector[1]);
for (int i = 2; i <= n; i ++) {
min_len_a[i] = min(min_len_a[i-1] + len_a[i], min_len_b[i-1] + len_b[i] + road_connector[i]);
min_len_b[i] = min(min_len_b[i-1] + len_b[i], min_len_a[i-1] + len_a[i] + road_connector[i]);
}
cout << min(min_len_a[n], min_len_b[n]);
}
Ivan Stevakin
Ivan Stevakin
69 560
Лучший ответ