滴滴0907-第二题

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	inputStr, _ := reader.ReadString('\n')
	inputStr = strings.TrimSpace(inputStr)
	inputArr := strings.Split(inputStr, " ")
	n, _ := strconv.Atoi(inputArr[0])
	k, _ := strconv.Atoi(inputArr[1])
	weights := make([][]int, k)
	for i := range weights {
		weights[i] = make([]int, 0)
	}
	for i := 0; i < k; i++ {
		inputStr, _ = reader.ReadString('\n')
		inputStr = strings.TrimSpace(inputStr)
		inputArr = strings.Split(inputStr, " ")
		for _, v := range inputArr {
			num, _ := strconv.Atoi(v)
			weights[i] = append(weights[i], num)
		}
	}
	message, _ := reader.ReadString('\n')
	message = strings.TrimSpace(message)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := 0; i < n-1; i++ {
		pre := int(message[i] - 'a')
		later := int(message[i+1] - 'a')
		dp[i][i+1] = weights[pre][later]
	}
	if n <= 2 {
		fmt.Print(dp[0][n-1])
		return
	}
	for j := 3; j < n; j++ {
		for i := j - 1; i >= 0; i = i - 2 {
			for p := i; p <= j; p = p + 2 {
				pre := int(message[p] - 'a')
				later := int(message[j] - 'a')
				d1, d2 := 0, 0
				if p > i {
					d1 = dp[i][p-1]
				}
				if p < j {
					d2 = dp[p+1][j-1]
				}
				dp[i][j] = max(dp[i][j], d1+weights[pre][later]+d2)
			}
		}
	}
	fmt.Print(dp[0][n-1])
}