How to solve this problem?

Revision en1, by 650iq, 2023-11-05 12:56:25

There are N towers arranged in a single line. You want to rearrange all the towers.

Given an array H of size N, where Hi denotes the height of tower i. You can rearrange this array in whatever way you like.

Beauty is defined as follows:

If j is the position of the tower i in the final arrangement, you add Hi*abs(i-j) to the Beauty.

Your task is to find the maximum Beauty you can achieve, after rearranging the towers.

I could only come with bitmask dp solution but here N is 10^3 so it won't work.


  Rev. Lang. By When Δ Comment
en1 English 650iq 2023-11-05 12:56:25 550 Initial revision (published)