题解 | #取数游戏#

package main

import (
	"bufio"
	"fmt"
    "os"
)

// dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[n-j+i]*A[i])
// dp[i][j-1] = max(dp[i][j-1], dp[i][j] + B[n-j+i]*A[j])
func main() {
   var in  = bufio.NewReader(os.Stdin)
   var out  = bufio.NewWriter(os.Stdout)
   defer out.Flush()

    var n int
    fmt.Fscan(in, &n)
    A, B := make([]int, n+1), make([]int, n+1)
    var dp = make([][]int, n+2)
    for i := 1; i<=n; i++ {
        dp[i] = make([]int, n+2)
        fmt.Fscan(in, &A[i])
    }
    dp[n+1] = make([]int, n+2) 
     for i := 1; i<=n; i++ {
        fmt.Fscan(in, &B[i])
     }

    ans := 0
     for i:= 1; i <= n; i++ {
        for j:=n; j>=i; j--{
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[n-j+i]*A[i])
            dp[i][j-1] = max(dp[i][j-1], dp[i][j] + B[n-j+i]*A[j])
        }
        ans = max(ans, dp[i][i-1])
     }

     for i:=1; i <= n; i++ {
        ans = max(ans, dp[i+1][i])
     }
     fmt.Fprintln(out, ans)
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}