每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出一行表示最大的乘积。
3 7 4 7 2 50
49
学习了各位大佬的代码,使用两个一维矩阵的java代码
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] val = new int[n]; for (int i = 0; i < n; i ++) { val[i] = sc.nextInt(); } int k = sc.nextInt(); int d = sc.nextInt(); System.out.println(helper(val, n, k, d)); } public static long helper(int[] val, int n, int k, int d){ long maxdp[] = new long[n + 1]; long mindp[] = new long[n + 1]; Arrays.fill(maxdp, 1); Arrays.fill(mindp, 1); // 遍历待选取的第k~第1名学生 for (int i = k - 1; i >= 0; i --) { // 第i名学生(1...i0...i1...n,i0<=j<=i1),j是第i名学生的下标,要求i的前面至少有i - 1个人 // 则j>=i, 要求i的后面至少有k-i个人,则n-j>=k-i,j<=n-k+i for (int j = i; j <= n - k + i; j ++) { // 前一名学生(i+1)可以是当前学生下标往后延顺d个,m=[j+1, j+d] for (int m = j + 1; m <= j + d && m <=n; m ++) { long temp1 = val[j] * maxdp[m]; long temp2 = val[j] * mindp[m]; maxdp[j] = Math.max(maxdp[j], Math.max(temp1, temp2)); mindp[j] = Math.min(mindp[j], Math.min(temp1, temp2)); } } } long res = Long.MIN_VALUE; for (long x: maxdp) { res = Math.max(x, res); } return res; } }
- import java.util.Scanner; //主要参考@菜鸡华的代码 //kk dd one命名引起不适所以替换成简洁有力的命名K D i //在N的遍历中使其终止与N-K+k,不进行剩下不必要的训练。 public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()) { //读数据 int N = sc.nextInt(); int[] arr = new int[N + 1]; for (int i = 1; i <= N; i++) { arr[i] = sc.nextInt(); } int K = sc.nextInt(); int D = sc.nextInt(); //规划数组表示,使用两个数组保证,最大正数最小负数都有保存 long[][] f = new long[N + 1][K + 1];//人直接对应坐标,n和K都要+1 long[][] g = new long[N + 1][K + 1]; //初始化k=1的情况 for(int i = 1;i<=N;i++){ f[i][1] = arr[i]; g[i][1] = arr[i]; } //自底向上递推 for(int k=2;k<=K;k++){ for(int i = k;i<=N-K+k;i++){ //求解当i和k定的时候,每步最优子问题 long tempmax = Long.MIN_VALUE; long tempmin = Long.MAX_VALUE; for(int left = Math.max(k-1,i-D);left<=i-1;left++){ if(tempmax<Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){ tempmax=Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i]); } if(tempmin>Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){ tempmin=Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i]); } } f[i][k] = tempmax; g[i][k] = tempmin; } } //从最后一行选取最终最大值 long result = Long.MIN_VALUE; for(int i = K;i<=N;i++){ if(result<f[i][K]){ result = f[i][K]; } } System.out.println(result); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int n = sc.nextInt(); int[] array = new int [n+1]; for (int i = 1; i <=n ; i++) { array[i] = sc.nextInt(); } int K = sc.nextInt(); int d = sc.nextInt(); long[][] fmax = new long[K+1][n+1]; long[][] fmin = new long[K+1][n+1]; long res = Integer.MIN_VALUE; for (int i = 1; i <=n; i++) { fmax[1][i] = array[i]; fmin[1][i] = array[i]; for (int k = 2; k <=K; k++) { for (int j = i-1 ; j > 0 && i-j<=d ; j--) { fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * array[i], fmin[k-1][j] * array[i])); fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * array[i], fmin[k-1][j] * array[i])); } } res = Math.max(res ,fmax[K][i]); } System.out.println(res); } sc.close(); } }
package challenge; import java.util.Scanner; /** * @author Eden * @version 创建时间:2018年7月21日 下午6:25:29 * @deprecated: * 题目描述 有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学 生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗? 输入描述: 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来 的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数, k 和 d (1 <= k <= 10, 1 <= d <= 50)。 输出描述: 输出一行表示最大的乘积。 */ public class Chorus { public static int[] arr;//学生能力数组 public static long[][][] resultArr;//resultArr[学生个数][已选择学生个数][最大/最小]暂存在第count次选择时它的最大与最小值 public static int k; public static int d; public static void main(String[] args){ Scanner input = new Scanner(System.in); int n = input.nextInt(); arr = new int[n]; for(int i=0;i<n;i++){ arr[i]=input.nextInt(); } k = input.nextInt();//选取学生个数 d = input.nextInt();//编号相隔最大距离 resultArr = new long[n][k+1][2]; long[] result; long max=0; for(int i=0;i<n-k+1;i++){ result = calculate(i,1); if(i==0) max=result[0]; else if(result[0]>max) max=result[0]; } System.out.println(max); } public static long[] calculate(int index,int count){ long[] result = {1,1}; if(count>k){ return result; } long max=arr[index],min=arr[index]; //选择编号相隔有限制,rear表示已当前学生index为基准,能选择后面最大学生编号 int rear = index+d+1; long firstTempResult,secondTempResult; if(rear>arr.length){ rear=arr.length; } //递归求解 for(int i=index+1;i<rear;i++){ if(resultArr[i][count][0]==0&&resultArr[i][count][1]==0){ firstTempResult = calculate(i,count+1)[0]*arr[index]; secondTempResult = calculate(i,count+1)[1]*arr[index]; }else{ firstTempResult = resultArr[i][count][0]*arr[index];; secondTempResult = resultArr[i][count][1]*arr[index]; } if(firstTempResult>max) max=firstTempResult; if(firstTempResult<min) min=firstTempResult; if(secondTempResult>max) max=secondTempResult; if(secondTempResult<min) min=secondTempResult; } result[0]=max; resultArr[index][count-1][0]=max; result[1]=min; resultArr[index][count-1][1]=min; //返回最大最小值 return result; } }
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
int n = Integer.parseInt(line);
line = scanner.nextLine();
String[] s = line.split(" ");
int arr[] = new int[n];
for (int i = 0;i < n;i ++) {
arr[i] = Integer.parseInt(s[i]);
}
line = scanner.nextLine();
String []s1 = line.split(" ");
int k = Integer.parseInt(s1[0]);
int d = Integer.parseInt(s1[1]);
dp(arr, k , d);
}
public static void dp(int []arr, int k, int d) {
//dp[i][j]表示以i为最后一个人的下标并且j为已选人数
//由于有正有负,所以两个数组一个存最大值一个存最小值
long [][]dpn = new long[arr.length][k + 1];
long [][]dpm = new long[arr.length][k + 1];
//以某个元素为结尾时的最大值
long max = Integer.MIN_VALUE;
for (int i = 0;i < arr.length;i ++) {
dpn[i][1] = arr[i];
dpm[i][1] = arr[i];
//因为一共要选k个人,所以这里再做一个循环
for (int kk = 2; kk <= k; kk ++) {
for (int j = i - 1; j >= 0 && i - j <= d;j -- ) {
//如果是正值,选大的
dpm[i][kk] = Math.max(dpm[i][kk], Math.max(dpm[j][kk - 1] * arr[i], dpn[j][kk - 1] * arr[i]));
//如果是负值,选小的
dpn[i][kk] = Math.min(dpn[i][kk], Math.min(dpm[j][kk - 1] * arr[i], dpn[j][kk - 1] * arr[i]));
}
}
max = Math.max(dpm[i][k], max);
}
System.out.println(max);
}
这个问题只要理解了从递归到动态规划的演变过程之后,就不难做出来了。
首先我们来看看递归的解题思路:
(cur:当前对象的下标,pre:上一次选择的对象的下标, count:已选择的人数,temp:当前乘积:result[0]:最终乘积)
对于n个人无非就是能不能选,以及选与不选的问题!
判断能不能选:需满足 cur - pre <= d
选与不选:就是递归的两个分支了
筛选结果:当count == k时,将当前乘积temp 与 最终乘积result[0] 择优存入result[0]中
递归出口:当cur >= n || count >= k时,由于筛选结果是在进入递归时的第一步操作,换言之,就是对上一次递归结果,进行筛选,所以当count==k时,已经可以返回了。
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] ability = new int[n]; for (int i = 0; i < n; i++) { ability[i] = sc.nextInt(); } int k = sc.nextInt(); int d = sc.nextInt(); long maxProduct = getMaxProduct(ability, k, d); System.out.println(maxProduct); sc.close(); } private static long getMaxProduct2(int[] ability, int k, int d) { if (ability.length == 1) { return ability[0]; } long[] result = { Long.MIN_VALUE }; int count = 0; int pre = -1; int cur = 0; long temp = 1; process(ability, k, d, count, pre, cur, temp, result); return result[0]; } /** * @param ability * @param k * @param d * @param count 表示已选人数 * @param pre 表示上一次选择的人的下标 * @param cur 表示当前的人的下标 * @param temp 用于保存当前乘积 * @param result 用于存储结果 * @return */ private static void process(int[] ability, int k, int d, int count, int pre, int cur, long temp, long[] result) { if (count == k) { result[0] = Math.max(temp, result[0]); } if (cur >= ability.length || count >= k) { return; } //可选 if (pre == -1 || cur - pre <= d) { //选 process(ability, k, d, count + 1, cur, cur + 1, temp * ability[cur], result); //不选 process(ability, k, d, count, pre, cur + 1, temp, result); } }
接下来分析一下怎么由递归演变到动态规划:
由于乘积,我们很容易想到,需要保存最大值和最小值(因为最大值可以=负数min,也可以=正数max)
所以开辟两个空间maxProduct和minProduct,然后只需要将递归过程中使用到的变量保存起来维护就好了。
如:
cur:就是i
pre:也是i
count:是j
temp:就是两个数组的值了
解释一下maxProduct[i][j]的含义:(maxProduct[i][j]类似)
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] ability = new int[n]; for (int i = 0; i < n; i++) { ability[i] = sc.nextInt(); } int k = sc.nextInt(); int d = sc.nextInt(); long maxProduct = getMaxProduct(ability, k, d); System.out.println(maxProduct); sc.close(); } private static long getMaxProduct(int[] ability, int k, int d) { long[][] maxProduct = new long[ability.length][k]; long[][] minProduct = new long[ability.length][k]; init(maxProduct, ability); init(minProduct, ability); for (int i = 1; i < ability.length; i++) { for (int j = 1; j < k; j++) { int start = i - d; start = start < 0 ? 0 : start; int end = i - 1; long maxTemp = getMaxFromMaxProduct(maxProduct, start, end, j - 1); long minTemp = getMinFromMinProduct(minProduct, start, end, j - 1); if (ability[i] == 0) { maxProduct[i][j] = 0; minProduct[i][j] = 0; } else if (ability[i] > 0) { maxProduct[i][j] = ability[i] * maxTemp; minProduct[i][j] = ability[i] * minTemp; } else { maxProduct[i][j] = ability[i] * minTemp; minProduct[i][j] = ability[i] * maxTemp; } } } long res = Long.MIN_VALUE; for (int i = 0; i < maxProduct.length; i++) { res = Math.max(res, maxProduct[i][k - 1]); } return res; } private static long getMinFromMinProduct(long[][] minProduct, int start, int end, int j) { long res = Long.MAX_VALUE; for (int i = start; i <= end; i++) { res = Math.min(minProduct[i][j], res); } return res; } private static long getMaxFromMaxProduct(long[][] maxProduct, int start, int end, int j) { long res = Long.MIN_VALUE; for (int i = start; i <= end; i++) { res = Math.max(maxProduct[i][j], res); } return res; } private static void init(long[][] arr, int[] ability) { for (int i = 0; i < arr.length; i++) { arr[i][0] = ability[i]; } for (int j = 0; j < arr[0].length; j++) { arr[0][j] = ability[0]; } }
这题可以从前递推,也可以从后递推,我选择的是从前递推的思路import java.util.Scanner;
import java.util.Scanner; public class Main { // 参考 【小刀初试】的算法思想, Java版本,便于理解 public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) { int n = cin.nextInt(); // n 个学生 int[] arr = new int [n+1]; for (int i = 1; i <=n ; i++) { arr[i] = cin.nextInt(); } int K = cin.nextInt(); // 选出K个 int d = cin.nextInt(); // 两个学生的位置编号的差不超过 d long[][] fmax = new long[K+1][n+1]; // 记录最大乘积 long[][] fmin = new long[K+1][n+1]; // 记录最小乘积 // fmax[k][i]表示 : 当选中了k个学生,并且以第i个学生为结尾,所产生的最大乘积; // fmin[k][i]表示 : 当选中了k个学生,并且以第i个学生为结尾,所产生的最小乘积; //初始化第一行 long res = Integer.MIN_VALUE; // 记得用Long类型,考虑数值范围 for (int i = 1; i <=n; i++) { fmax[1][i] = arr[i]; fmin[1][i] = arr[i]; for (int k = 2; k <=K; k++) { for (int j = i-1 ; j > 0 && i-j<=d ; j--) { fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i])); fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i])); } } res = Math.max(res ,fmax[K][i]); } System.out.println(res); } } }