10月26日,北京站源创会,聊聊高性能计算与大模型推理
题目描述
小明有一个长度为n,由前k个小写英文字母组成的字符串(保证n为偶数)。
小亮想在小明睡觉的时候把这个字符串用小明的零花钱消除干净。小亮每次可以选择该串的两个相邻的字符删除,删除后将串拼上,并花掉小明一定数量的零花钱。若某一次删除的相邻两个字符从左到右分别是a和b,则将花掉小明cost(a,b)块钱。小亮希望他花掉的零花钱尽可能多,帮帮小亮。
输入描述
第一行有两个整数n,k(1
接下来k行给出了一个k*k的由整数构成的矩阵。矩阵中第i行第j列的元素代表消除相邻的第i个字母和第j个字母所能花掉的钱数。
最后一行有一个长度为n的字符串,代表小明的字符串。
注意:
矩阵中的i,j从0开始计数,第i个字母表示相对于字母a来计数,如a为第0个字母,b为第1个字母。
输出描述
输出一个值,代表小亮最多能花掉小明多少零花钱。
题解
import java.util.*;
class Main {
static Map cache = new HashMap();
static int[][] arrCost;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
// 如果n小于2,则直接输出0并退出程序
if (n =end) {
return 0;
}
// 如果子字符串长度为2,则直接计算成本并返回
if (end - begin == 1) {
return getCost(strArr[begin], strArr[end]);
}
// 初始化最大成本为0
int max = 0;
// 遍历begin到end之间的所有可能分割点
for (int i = begin+1; i