Каков наилучший подход к дп для вопроса TRT (угощение для коров) спой?

Question

FJ приобрела N (1 <= N <= 2000) вкусных угощений для коров, которые получают деньги за выдачу огромного количества молока. FJ продает одно угощение в день и хочет максимизировать деньги, которые он получает за определенный период времени. Угощения интересны по многим причинам: </p>

Угощения нумеруются 1..N и хранятся последовательно в одном файле в длинном ящике, открытом на обоих концах. В любой день FJ может получить одно угощение с любого конца своего лакомства. Подобно изысканным винам и вкусным сырам, угощения улучшаются с возрастом и устанавливают более высокие цены. Угощения не единообразны: некоторые из них лучше и имеют более высокую внутреннюю ценность. Обработка i имеет значение v (i) (1 <= v (i) <= 1000). Коровы платят больше за лакомства, которые выдерживаются дольше: корова будет платить v (i) * a за лакомство возраста Учитывая значения v (i) каждого из угощений, выстроенных в порядке индекса i в их ящике, какое наибольшее значение FJ может получить для них, если он прикажет их продажу оптимальным образом? </p>

Первое угощение продается в день 1 и имеет возраст а = 1. Каждый последующий день увеличивает возраст на 1.

Input Строка 1: одно целое число, N

Строки 2..N + 1: Строка i + 1 содержит значение лечения v (i)

Выход Максимальный доход, который FJ может достичь, продавая лакомства

Пример Входные данные: 5

1 3 1 5 2

Выход: 43

Каков основной подход к дп в этой проблеме и как мне обработать возраст в матрице дп ...? Единственный подход, который мне запомнился, - рекурсивный ... Я новичок в DP, и у меня возникли некоторые базовые проблемы с DP, но это не в моем уме ... Это то, что я пытался до сих пор

int give(int a[],int x,int y,int age)
{

if(x==y) return age*a[x];

return max(age*a[x]+give(a,x+1,y,age+1),age*a[y]+give(a,x,y-1,age+1));

}

x = начальный индекс, инициализируется от 0, y = последний индекс, n-1, возраст = 1 при первом вызове

Answer 1

Первое, на что нужно обратить внимание, это то, что текущее состояние не зависит от истории того, откуда мы принимали угощение.Единственное, что нас волнует, это то, сколько раз мы принимали угощение слева и сколько раз мы взяли его справа.

Поэтому состояние можно кодировать всего двумя числами: смещение влево и смещение вправо,

Пусть f(i,j) будет суммой денег, которую мы можем получить, если не продадим текущий ход.Мы знаем, что там мы уже взяли i+j объектов из линии, поэтому возраст также равен i+j.

Поэтому нам просто нужно проверить, какую позицию мы хотим занять, и выбрать лучшую.Хорошо, если мы выберем угощение слева, наша сумма будет

cost * time + f( i + 1 , j ) = cost * (i + j) + f( i + 1 , j ).

Сумма, если взять справа, имеет очень похожую формулу

cost_right * (i + j) + f( i , j + 1 ).

Поэтому мы можем знать, f(i+1,j) и f(i,j+1) вычислить f(i,j).

Что ж, это можно сделать с помощью динамического программирования, сохраняя двумерный массив размером n*n, в котором хранится либо -1, если f(i,j) неизвестно, либо значение f(x,y), если оно известно.Затем вы можете просто обновить рекурсивный метод, описанный выше, чтобы фактически сохранить результаты и вернуть решение, если оно уже известно.Если мы посмотрим на ваш пример кода, мы можем изменить его для своевременного выполнения.

    int give(int a[],int x,int y,int age)
    {
        if(dp[x][y]!=-1) return dp[x][y];
        if(x==y) return age*a[x];

        int answer=max(age*a[x]+give(a,x+1,y,age+1),age*a[y]+give(a,x,y-1,age+1));

        dp[x][y]=answer;
        return answer;
    }

Это всего лишь фрагмент, так как вам нужно исправить граничные условия и создать реальный глобальный массив dp, но я надеюсь, что этого достаточно для начала.