мандрагора маг решил распределить свое богатство между своими лучшими друзьями Лотаром и Магноном, теперь у него есть N монет, каждая из которых имеет некоторое значение A [i] (i <= i <= N), будучи великим волшебником, мандрагора может изменитьстоимость монет, кроме первой и последней. Он может изменить значение i-й монеты на половину суммы (i-1) -й и (i + 1) -й монеты, но для этого необходимо выполнить два условия: </p>
1-значение как i-1, так и i + 1 монеты должно быть четным, а 2 - если значение j-й монеты изменяется после i-го достоинства монеты, то j> i
Теперь он распределит свое богатство так, что онотдаст одну монету от спины к лотару и одну монету от фронта к магнону. Будем продолжать это, пока все монеты, которыми он владеет, не будут распределены. Учтите, что в случае нечетного числа монет он отдаст свою среднюю монету другому другу, тхочет максимизировать абсолютную разницу в стоимости монет, отданных Лотару и Магнону
пример-> 10
5 6 5 2 1 7 9 7 2 5
этимногократные случаи для значений монеты, основанные на правилах мага 1.5 6 5 2 1 7 9 7 2 5 2.5 6 4 2 1 7 9 7 2 5
разность абсолютных значений case1- | 5-5 | + | 6-2 | + | 5-7 | + | 2-9 | + | 1-7 | = 19 случай абсолютной разности 2 = | 5-5 | + | 6-2 | + | 4-7 | + | 2-9}+ | 1-7 | = 20, поэтому ответ 20
Я попробовал описанный ниже подход, но компилятор просит меня дополнительно его оптимизировать. Я думаю, что динамическое программирование может быть использовано, но не может понятьлюбая подзадача, которая повторяется. Может ли кто-нибудь помочь?
#include<bits/stdc++.h>
using namespace std;
int helper(int *l,int j,int n)
{/*
int l[n];
for(int i=0;i<n;i++)
{
l[i]=input[i];
}*/
if(j==n)
{
int sum=0;
int k=0;
while(k<n/2)
{
sum+=abs(l[k]-l[n-1-k]);
k++;
}
return sum;
}
int nc=helper(l,j+1,n);
int c=0;
if(j-1>=0 && j+1<n &&(l[j-1]%2==0&& l[j+1]%2==0))
{
l[j]=(l[j+1]+l[j-1])/2;
int c=helper(l,j+1,n);
}
int b=max(c,nc);
return b;
}
int main()
{
int a[10]={5,6,5,2,1,7,9,7,2,5};
cout<<helper(a,0,10)+1;
/*for(int i=0;i<1000;i++)
{
memo[i]=-1;
}*/
}
enter code here