E : Active Infants
Problem Statement - here
Solution :
To make ourselves clear, we can rearrange them in any order we like. So, it is clear that for every element we have to keep it as far as possible from its current position. But wait, our first priority should be the one who has maximum weight, because it contributes maximum to our happiness. So, we should sort the weights in decreasing order and then what?
Let's say we are at the ith index of our sorted weights, whose initial position is ind and its weight is w. We have already placed our (i-1) elements. These elements are either to the very start or the very end of our array. So, this ith element will either come in front or at back. Let's say we have already placed L elements to left and R elements to right, then L+R = i-1.
so the transitions are now very easy to write:
dp[L+1][R] = max(dp[L+1][R],dp[L][R] + abs(L+1 - ind)*w)
dp[L][R+1] = max(dp[L][R],dp[L][R+1] + abs(n - R- ind)*w)
We can simply loop till i-1 assuming the current index as the number of elements placed to Left (L) first and calculate the first transition table and then assume it as #elements to the right (R) and calculate the second transition table.
The Implemented Code:
ll dp[2005][2005] = {};
void solve()
{
ll n;
cin>>n;
pll a[n+1];
rep(i,1,n+1) cin >> a[i].F , a[i].S = i;
sort(a+1,a+n+1,greater<pll>());
rep(i,1,n+1){
rep(j,0,i){
ll L = j;
ll R = i-1-j;
dp[L+1][R] = max(
dp[L+1][R],
dp[L][R] + abs(L+1 - a[i].S)*a[i].F
);
R = j;
L = i-1-j;
dp[L][R+1] = max(
dp[L][R+1],
dp[L][R] + abs(n - R - a[i].S)*a[i].F
);
}
}
ll ans = 0;
rep(i,0,n+1){
ans = max(ans,dp[i][n-i]);
}
cout << ans << endl;
}
