滴滴笔试零花钱

比如[a, b, c, d, e, f]这个数组,a可以和b、d、f消除,枚举遍历可消除的元素,分治递归计算出最大花费的值。

对于同一个区间花费的零花钱的值的最大值是相同的,所以记得加上记忆化搜索,否则正确率是27%

import java.util.*;

public class Main {
    static Map<String, Integer> 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();
        if (n < 2) {
            System.out.println(0);
            return;
        }
        int[][] arr = new int[k][k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        arrCost = arr;
        String str = sc.next();
        char[] strArr = str.toCharArray();
        int ans = getMaxConst(strArr, 0, n-1);
        System.out.println(ans);
    }

    private static int getMaxConst(char[] strArr, int begin, int end) {
        StringBuilder sb = new StringBuilder();
        String key = sb.append(begin).append("-").append(end).toString();
        if(cache.containsKey(key)) {
            return cache.get(key);
        }
        if(begin>=end) return 0;
        if (end - begin == 1) {
            return getCost(strArr[begin], strArr[end]);
        }
        int max = 0;
        for (int i = begin+1; i <= end; i+=2) {
            max = Math.max(max, getCost(strArr[begin], strArr[i])+getMaxConst(strArr, begin+1, i-1)+getMaxConst(strArr, i+1, end));
        }
        cache.put(key, max);
        return max;
    }

    private static int getCost(char a, char b) {
        int ai = a - 'a';
        int bi = b - 'a';
        return arrCost[ai][bi];
    }

}
全部评论
同记搜,0.27😅
点赞 回复 分享
发布于 09-07 18:48 辽宁
区间dp没写出来
点赞 回复 分享
发布于 09-07 19:17 浙江
0.27😭
点赞 回复 分享
发布于 09-07 20:07 湖北
本来用dp写,最后发现思路不对,但是还是混了27
点赞 回复 分享
发布于 09-07 21:11 上海
请问为什么dfs的时候,为什么要用begin和i来合并,可以用i和i+1来合并吗
点赞 回复 分享
发布于 09-07 22:32 北京
牛的 dp做的 写到一半发现思路不对,只过了9%
点赞 回复 分享
发布于 09-09 10:40 北京

相关推荐

昨天 13:31
怀化学院 Java
勇敢牛牛不怕难:又疯一个
点赞 评论 收藏
分享
9 17 评论
分享
牛客网
牛客企业服务