Overview

This problem asks us to arrange paintings in a row and maximize the total sum of products of the difference in tone values between adjacent paintings and the wall weights.

Analysis

There are \(N!\) permutations for arranging \(N\) paintings in a row. Since the maximum value of \(N\) is 16, an exhaustive search would require \(16! \approx 2.0 \times 10^{13}\) iterations, making a naive brute-force approach infeasible. Therefore, we use dynamic programming (DP) to search efficiently. A key observation is that the evaluation value depends on pairs of adjacent paintings, so we can compute efficiently by maintaining partial placement information as our state — specifically, which paintings have already been placed and which painting was placed last.

Algorithm

We use bitmask DP. The state is defined by “the set of already placed paintings (bitmask)” and “the index of the last placed painting,” and we maintain the maximum evaluation value for each state. Specifically, let \(dp[state][last]\) be the maximum evaluation value when the set of placed paintings is \(state\) (in bit representation) and the last placed painting is \(last\). For state transitions, we select an unplaced painting \(next\) and update the evaluation value for the new state \(new\_state = state | (1 << next)\). The added evaluation value is \(|P[last] - P[next]| \times W[k-1]\), where \(k\) is the current number of placed paintings. The answer is the maximum value among all states where all paintings have been placed (\(state = (1<<n)-1\)).

Complexity

• Time complexity: \(O(2^N \times N^2)\)
• Space complexity: \(O(2^N \times N)\)

Implementation Details

• We use bitmasks to manage states. The number of states is \(2^N\), and for each state we maintain \(N\) possibilities for the last painting, so the two-dimensional array size is \(2^N \times N\).

• For the initial state, we initialize the evaluation value to 0 for states where each painting is placed alone (bitmask with exactly one bit set).

• During state transitions, we distinguish between used and unused paintings in the current state, and try each unused painting in order to update the evaluation value.

• Finally, we find the maximum value among states where all bits are set (all paintings have been placed).

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1:1+n]))
    W = list(map(int, data[1+n:1+n+(n-1)]))
    
    total_states = 1 << n
    dp = [[-1] * n for _ in range(total_states)]
    
    for i in range(n):
        dp[1 << i][i] = 0
        
    for state in range(total_states):
        k = bin(state).count('1')
        if k == 0:
            continue
        for last in range(n):
            if dp[state][last] == -1:
                continue
            for next in range(n):
                if state & (1 << next):
                    continue
                new_state = state | (1 << next)
                add = abs(P[last] - P[next]) * W[k-1]
                if dp[new_state][next] < dp[state][last] + add:
                    dp[new_state][next] = dp[state][last] + add
                    
    ans = max(dp[total_states-1])
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.