В замке Камелот пришло время ужина, и грозные рыцари Круглого стола требуют десерта. Вы, повар, находитесь в супе. Есть N рыцарей, включая короля Артура, каждый из которых предпочитает десерт по-своему, но вы не можете позволить себе приготовить десерты для всех из них.
Вам дана стоимость производства любимых рыцарей каждого рыцаря. десерт – поскольку это круглый стол, список начинается со стоимости десерта короля Артура и идет против часовой стрелки.
Вы решаете выбрать самые дешевые десерты, чтобы из каждой пары соседних рыцарей хотя бы один получает свой десерт. Это гарантирует, что рыцари не будут протестовать.
Какова минимальная стоимость сегодняшнего ужина при таких условиях?
Например, предположим, что есть 5 Рыцарей, а их десерты стоят 1, 2, 1, 2 и 2. В этом случае минимальная стоимость равна 4, чего вы можете добиться, накормив первого, третьего и четвертого (или пятого) Рыцарей.Формат ввода
Есть 2 строки ввода. В первой строке записано одно целое число N — количество мест за столом. Следующая строка содержит N целых чисел, разделенных пробелами, каждое из которых представляет собой стоимость десерта рыцаря, перечисленного в порядке против часовой стрелки вокруг стола, начиная с короля Артура.
Формат вывода
Результат должен представлять собой одну строку, содержащую одно целое число, минимальную возможную стоимость для вас, шеф-повар.
Я пытался решить эту проблему с помощью динамического программирования, но я просто не могу понять. что я здесь делаю не так. Вот мой код:
Код: Выделить всё
#include
#include
using namespace std;
int solve(int arr[], int n) {
if (n == 1) {
return arr[0];
}
if (n == 2) {
return min(arr[0], arr[1]);
}
vector dp1(n, 0);
vector dp2(n, 0);
// Case 1: Considering the first knight, exclude the last (dp1)
dp1[0] = arr[0];
// dp1[1] = min(arr[0], arr[1]);
for (int i = 1; i < n - 1; i++) {
if(i > 1){
dp1[i] = min(arr[i] + dp1[i - 2], dp1[i - 1]);
}
else {
dp1[i] = min(arr[i] + dp1[0], dp1[i - 1]);
}
}
// Case 2: Considering the last knight, exclude the first (dp2)
dp2[1] = arr[1];
for (int i = 2; i < n; i++) {
if(i > 2){
dp2[i] = min(arr[i] + dp2[i - 2], dp2[i - 1]);
}
else {
dp2[i] = min(arr[i] + dp2[0], dp2[i - 1]);
}
}
// We need the minimum cost covering the circle, thus choose the best between
// excluding the first knight and excluding the last knight
return min(dp1[n - 2], dp2[n - 1]);
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout
Подробнее здесь: [url]https://stackoverflow.com/questions/79036254/i-cant-figure-out-how-to-solve-this-competitive-programming-problem[/url]