美团4.8笔试题，水果打包

水果打包
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美不干外卖配送了，转行开了一家水果店。

一天她接到了一个大单，客户订购了 n 个水果，并且要求打包成多个果篮，一个果篮最多装 m 个水果。

为了包装方便，水果按从 1 到 n 编号，同一个果篮里装的水果编号必须是连续的。果篮的成本与容积成线性关系。为了估计容积，小美简单地用样本中点估计了一下。具体来说，假设一个果篮中装的最大的水果体积是 u，最小的是 v，那么这个果篮的成本就是 k × floor((u+v)/2) + s，其中 k 是果篮中装入水果的个数，s 是一个常数，floor(x) 是下取整函数，比如 floor(3.8)=3, floor(2)=2。

客户并没有规定果篮的数量，但是希望果篮的成本越小越好，毕竟买水果就很贵了。请求出小美打包这 n 个水果所用的最小花费。

输入描述

第一行三个正整数 n, m, s。意义如题面所示。

第二行 n 个正整数 a1, a2, …, an，表示每个水果的体积。

对于全部数据，1 ≤ n ≤ 104, 1 ≤ m ≤ 103, m ≤ n, 1 ≤ ai, s ≤ 104。

输出描述

输出一个整数，表示打包这 n 个水果果篮的最小成本。

样例输入

6 4 3
1 4 5 1 4 1

样例输出

21

提示

样例说明

前三个水果装成一个果篮，后三个水果装成一个果篮。

代码：
一维动态规划，但每个格子包括多种可能

import java.util.Scanner;/*** @ClassName: meituan03* @Description: TODO* @Author: ChiKin Lau @ SUSE* @Date: 2023/4/9 14:47* @version: 1.0**/
public class meituan03 {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int s = in.nextInt();int[] a = new int[n];int[] dp = new int[n+1];for (int i = 0; i < n; i++) {a[i] = in.nextInt();dp[i+1] = Integer.MAX_VALUE;  //装i个水果的最小成本}//dp[i]=min(dp[i-1]+cost[1],dp[i-2]+cost[2],...,dp[i-m]+cost[m]),cost[]的max和min通过反向循环得到for (int i = 1; i <= n; i++) {int max = a[i-1], min = a[i-1];for (int j = 1; j <= m && j <= i; j++) {max = Math.max(max, a[i-j]);min = Math.min(min, a[i-j]);int cost = j*((max+min)/2)+s;dp[i] = Math.min(dp[i], dp[i-j]+cost);}}System.out.println(dp[n]);}
}