题解 | #取数游戏#

对区间动态规划。

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))[::-1]

# dp[i][j]是这一族问题中输入为aa[i:j+1]和bb[i:j+1]时的解。
dp = [[0 for j in range(n)] for i in range(n)]

# 初始化：最小的子问题就是n=1的情况，总共只有一种可能。
for idx in range(n):
    dp[idx][idx] = aa[idx] * bb[0]

# 动态规划：只有两种可能，要么当前区间的左端点是新取的点，要么当前区间的右端点是新取的点
for i in range(n)[::-1]:
    for j in range(i+1,n):
        dp[i][j] = max(dp[i][j-1]+bb[j-i]*aa[j], dp[i+1][j]+bb[j-i]*aa[i])
        
print(dp[0][-1])