阿里云3.24笔试第三题

自己用的二维dp超内存了,正确应该是贪心

import java.util.*;

public class Aliyun324_3 {

    public static void main(String[] args) {
        //阿里云3.24笔试 第三题
        //n个城市,从1号城市到n号城市,每到达一个城市消耗1单位粮食
        //输入n个数,表示每个城市粮食的单价。粮食无上限
        //可以携带额外的的粮食,在移动时超过1单位的额外粮食要支付运费,每单位支付1
        //求最小的支付金额

        //输入示例
        //4
        //1 3 2 4
        //输出:5
        //贪心做法: dp[i] = dp[i - 1] + Math.min(i - 1 - j + prices[j]) 对于:1 <= j <= i - 1
        //贪心的地方在于对于i处,要选取之前城市中的价格最低的(包含上运费)
        //dp[i]表示到达城市i所需要的最小花费
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] prices = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prices[i] = in.nextInt();
        }
        for (int i = 2; i <= n; i++) { //从第二个城市开始
            int minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= i - 1; j++) { //检索第i个城市之前的最小花费,运费是i-1-j
                minVal = Math.min(minVal, i - 1 - j + prices[j]);
            }
            dp[i] = dp[i - 1] + minVal;
        }
        System.out.println(dp[n]);
    }
}

全部评论
今天做的这个,正常二维只能过26
点赞
送花
回复
分享
发布于 03-24 20:33 新加坡
看懂了谢谢大佬,确实应该是贪心
点赞
送花
回复
分享
发布于 03-25 14:46 北京
滴滴
校招火热招聘中
官网直投

相关推荐

6 9 评论
分享
牛客网
牛客企业服务