滴滴笔试0907

对比之美

小美正在摆放她的收藏品。小美有一个漂亮的收藏架，有着一排n个格子，从左到右内存限制:分别编号为1 2…n。小美打算把她的m个收藏品放进这n个格子之中，并且尽可能摆放地好看。怎样才算好看呢?小美认为有对比才有美感，相邻两个格子收藏品数量之差越大就越美。形式化地讲，我们认为如果第i个格子里摆放了a,个收藏品，那么美观度为∑”|ai- a（i-1）|，小美觉得有些格子不放收藏品也可以接受，即要求a¡≥0，求和ai=m,请帮小美想出最美观的摆放方案 注意，||表示x的绝对值，|-5|=5,|3|=3。

一共三种情况，当n==1时只能是0，当m是2时候只能是2，除此之外只能是2m

public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n=sc.nextInt();
            int m=sc.nextInt();
            if(n==1){
                System.out.println(0);
            }else if(n==2){
                System.out.println(2);
            }else {
                System.out.println(2*m);
            }
        }
   }      
}

字符消除

小明有一个长度为n，由前k个小写英文字母组成的字符串(保证n为偶数)

小亮想在小明睡觉的时候把这个字符串用小明的零花钱消除干净。小亮每次可以选择该串的两个相邻的字符删除，删除后将串拼上，并花掉小明一定数量的零花钱。若某一次删除的相邻两个字符从左到右分别是a和b，则将花掉小明cost(a,b)块钱。小亮希望他花掉的零花钱尽可能多，帮帮小亮

输入描述：第一行有两个整数n,k(1<=n<=500,1<=k<=26)，分别代表小明的字符串长度与字符串中的字符种类数(保证n为偶数且串的内容仅由前k个小写英文字母组成)。接下来k行给出了一个k*k的由整数构成的矩阵。矩阵中第i行第j列的元素代表消除相邻的第i个字母和第j个字母所能花掉的钱数。

最后一行有一个长度为n的字符串，代表小明的字符串。

代码看着敲得牛友单纯用来学习@冰雪灬独舞

public class Main2 {
    static Map<String,Integer> map=new HashMap<>();//定义了一个静态的HashMap来存储已经计算过的结果，以避免重复计算。
    static  int[][] ans;//静态的二维数组ans来存储成本矩阵
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入 n 和 k
        int n = sc.nextInt();
        int k = sc.nextInt();
        if(n<2) {
            System.out.println(0);
            return;
        }

        // 输入 k*k 的成本矩阵
        int[][] cost = new int[k][k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                cost[i][j] = sc.nextInt();
            }
        }
        // 输入字符串
        String s = sc.next();
        ans=cost;
        char[] charArray = s.toCharArray();
        int res=getMaxCost(charArray,0,n-1);
        System.out.println(res);

    }

    private static int getMaxCost(char[] charArray, int start, int end) {
        StringBuilder stringBuilder = new StringBuilder();
        String key = stringBuilder.append(start).append("-").append(end).toString();
        //如果该键已经存在于HashMap中，说明之前已经计算过该子串的最大成本
        if (map.containsKey(key)) {
            return map.get(key);
        }
        //如果子串的起始位置大于等于结束位置，说明当前子串为空，所以返回0
        if (start >= end) {
            return 0;
        }
        //我们判断如果起始位置和结束位置相差为1，说明当前子串只有两个字符，所以直接调用getCost函数返回该字符对应的成本。
        if (end - start == 1) {
            return getCost(charArray[start],charArray[end]);
        }
        //递归调用getMaxCost函数分别计算左子串和右子串的最大成本，并将这两部分的成本累加起来，再加上将起始位置字符和分割点字符进行配对时的成本。
        int res = 0;
        for (int i = start+1; i <=end; i+=2) {
            res = Math.max(res, getCost(charArray[start], charArray[i]) + getMaxCost(charArray,start+1,i-1) + getMaxCost(charArray,i+1,end));
        }
        //将计算得到的最大成本存入HashMap中，并返回该最大成本。
        map.put(key,res);
        return res;
    }

    private static int getCost(int start, int end){
        int a=start-'a';
        int b=end-'a';
        return ans[a][b];
    }
}