Задача №1615. Замена робота
Дан новый промышленный робот, максимальный срок службы которого не ограничен. Однако, все механизмы со временем теряют свою ценность, производительность и требуют больше затрат на ремонт. Известно, что затраты на обслуживание робота в \(i\)-м году от начала эксплуатации составляют \(C_i\), прибыль, которую приносит робот за \(i\)-й год своей работы составляет \(P_i\). Также в конце любого года можно продать старого робота и купить нового. Цена нового робота не зависит от времени и равна \(S\). Цена подержанного робота, прослужившего \(i\) лет равна \(R_i\). Определите оптимальный график замены роботов в течение \(N\) лет (то есть чтобы суммарная прибыль от использования была максимальна).
в первой строке вводятся числа \(N\) – расчетный период времени (натуральное, не превышает 100) и \(S\) (натуральное, не превышает \(10^5\)) – цена нового робота. В следующей строке указано \(N\) чисел (натуральные, не превышают 500) – затраты на обслуживание робота в течение соответствующего года. В следующей строке следует еще \(N\) чисел (натуральные, не превышают 500) - прибыль, которую приносит робот в соответствующие годы, затем еще \(N\) чисел (натуральные, не превышают 500) – цена подержанного робота, в зависимости от возраста.
Выведите максимальную прибыль, которую можно получить к концу \(N\)-го года, при оптимальной смене роботов.
Обратите внимание: рассматривается только операция замены робота. То есть если в конце \(N\)-го года вы решите продать робота, то это означает автоматическую покупку нового. То есть робот, проданный после расчетного периода чистой прибыли не приносит.
если робот работает 2 года без замены, то он приносит прибыли на 100+95=195 и требует 2+3=5 на обслуживание; если мы решим в конце 1-го года заменить робота на нового, то мы получим: 100+100=200 (новый робот будет приносить прибыль 100, так как работает 1-й года) + 90 (выручка от продажи старого робота) мы потеряем: 2+2=4 (новый робот также будет требовать затрат за свой первый год) -100 – уплатим за нового робота итого +200+90-100-4=186. Следовательно, первый вариант предпочтительнее
2 100 2 3 100 95 90 80
190