首页 > 腾讯笔试第一题:木棍合并为什么过不了?
头像
宇酱ne
编辑于 2020-08-23 22:31
+ 关注

腾讯笔试第一题:木棍合并为什么过不了?

rt,一个区间dp,自测数据都没问题,就是过不了,哪位大哥帮我看看哪里写错了。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] res = new int[T];
        for(int i = 0; i < T; i++){
            int n = sc.nextInt();
            int[] a = new int[n+1];
            int[] sum = new int[n+1];
            int[][] dp = new int[n+1][n+1];
            for(int j = 0; j <= n; j++){
                Arrays.fill(dp[j], Integer.MAX_VALUE);
            }
            sum[0] = 0;
            for(int j = 1; j <= n; j++){
                a[j] = sc.nextInt();
            }
            for(int j = 1; j <= n; j++){
                sum[j] = a[j] + sum[j-1];
            }
            for(int j = 1; j <= n; j++){
                dp[j][j] = 0;
            }
            for(int k = 1; k < n; k++){
                for(int j = 1; j+k <= n; j++){
                    int m = k + j;
                    for(int x=j; x<m; x++){
                        dp[j][m] = Math.min(dp[j][m], dp[j][x] + dp[x+1][m] + sum[m] - sum[j-1]);
                    }
                }
            }
            res[i] = dp[1][n];
        }
        for(int r : res){
            System.out.println(r);
        }
    }
}

全部评论

(8) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐