每个输入包含 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
while 1: try: n = int(raw_input()) A = map(int, raw_input().split()) k, d = map(int, raw_input().split()) except: break B = [[[0] * 2 for j in range(n)] for i in range(k + 1)] for k in range(1, k + 1): for i in range(n): if k == 1 or i == 0: B[k][i][0], B[k][i][1] = A[i], A[i] else: M = [] for t in range(1, d + 1): if i - t < 0: break D = B[k - 1][i - t] M.extend([D[0] * A[i], D[1] * A[i]]) B[k][i][0], B[k][i][1] = min(M), max(M) print max([B[k][i][1] for i in range(n)])
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n; while (cin >> n){ vector<int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } int k, d; cin >> k >> d; vector<vector<long long>> dp_max(n, vector<long long>(k + 1, 0)); vector<vector<long long>> dp_min(n, vector<long long>(k + 1, 0)); for (int i = 0; i < n; i++){ dp_max[i][1] = a[i]; dp_min[i][1] = a[i]; } for (int i = 0; i < n; i++){ for (int j = 2; j <= k; j++){ for (int m = max(0, i - d); m <= i - 1; m++){ dp_max[i][j] = max(dp_max[i][j], max(dp_max[m][j - 1] * a[i], dp_min[m][j - 1] * a[i])); dp_min[i][j] = min(dp_min[i][j], min(dp_min[m][j - 1] * a[i], dp_max[m][j - 1] * a[i])); } } } long long max_value = dp_max[k - 1][k]; for (int i = k; i < n; i++){ max_value = max(max_value, dp_max[i][k]); } cout << max_value << endl; } return 0; }
import java.util.*;
5
-8 6 7 -7 9
3 50
i=1时fm和fn只能取到k=1,i=1记录过程结果 | ||||||
Max: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
Min: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
i=2时,fm和fn只能取到k=2,i=2保存结果 | ||||||
Max: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
Min: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 0 | 0 | 0 |
2 | 0 | 0 | -48 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
i=3时,fm和fn根据之前保存结果计算结果 | ||||||
Max: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | 0 | 0 |
2 | 0 | 0 | 0 | 42 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
Min: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | 0 | 0 |
2 | 0 | 0 | -48 | -56 | 0 | 0 |
3 | 0 | 0 | 0 | -336 | 0 | 0 |
i=4时,fm和fn根据之前保存结果计算结果 | ||||||
Max: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | -7 | 0 |
2 | 0 | 0 | 0 | 42 | 56 | 0 |
3 | 0 | 0 | 0 | 0 | 392 | 0 |
Min: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | -7 | 0 |
2 | 0 | 0 | -48 | -56 | -49 | 0 |
3 | 0 | 0 | 0 | -336 | -294 | 0 |
i=5时,fm和fn根据之前保存结果计算结果 | ||||||
Max: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | -7 | 9 |
2 | 0 | 0 | 0 | 42 | 56 | 63 |
3 | 0 | 0 | 0 | 0 | 392 | 504 |
Min: | ||||||
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | -8 | 6 | 7 | -7 | 9 |
2 | 0 | 0 | -48 | -56 | -49 | -72 |
3 | 0 | 0 | 0 | -336 | -294 | -504 |
| ||||||
| |
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] nums = new int[n]; for(int i = 0; i < n; i++){ nums[i] = scan.nextInt(); } int k = scan.nextInt(); int d = scan.nextInt(); long[][] max = new long[k][n]; long[][] min = new long[k][n]; for(int i = 0; i < k; i++) for(int j = 0; j < n; j++){ //min[i][j] = Integer.MAX_VALUE; max[i][j] = 1; if(i == 0){ min[i][j] = nums[j]; max[i][j] = nums[j]; } } for(int i = 1; i < k; i++) for(int j = 0; j < n; j++) for(int m = 1; m <= d; m++){ if(j - m >= 0){ if(nums[j] > 0){ min[i][j] = Math.min(min[i][j], min[i - 1][j - m] * nums[j]); max[i][j] = Math.max(max[i][j], max[i - 1][j - m] * nums[j]); } else{ min[i][j] = Math.min(min[i][j], max[i - 1][j - m] * nums[j]); max[i][j] = Math.max(max[i][j], min[i - 1][j - m] * nums[j]); } } } long Max = 0; for(int i = 0; i < n; i++) Max = Math.max(Max, max[k - 1][i]); System.out.println(Max); } }
1、最大的乘积可能来自之前的最大乘积 * 当前的数值,也有可能来自之前的最小乘积 * 当前的数值,因此使用两个数组maxdp和mindp来记录当前位置处的最大和最小的乘积。
2、maxdp[i][j]表示,在必须以选择第i个同学为结尾的情况下选择j个同学的最大乘积。maxdp[i][j]的值可能来自:
max(maxdp[i-1][j-1]*arr[i], mindp[i-1][j-1]*arr[i])
max(maxdp[i-2][j-1]*arr[i], mindp[i-2][j-1]*arr[i])
...
max(maxdp[i-d][j-1]*arr[i], mindp[i-d][j-1]*arr[i])
选择最大的一个即可。
其中,maxdp[i-?][j-1]表示在i位置之前,以某一位置为结尾时选择j-1个同学的最大乘积,该位置需要满足两个条件:和j的距离不能超过d、该位置之前(包含该位置)必须至少有j-1个同学。
3、mindp与之类似。
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
long long process(vector<int> array,int n,int k, int d)
{
vector<long long> tmp(k+1, 0);
vector<vector<long long>> maxdp(n+1, tmp);
vector<vector<long long>> mindp(n+1, tmp);
for(int i=1; i<=n; i++)
{
maxdp[i][1] = array[i-1];
mindp[i][1] = array[i-1];
}
for(int i=2; i<=n; i++)
{
for(int j=2; j<=k && j<=i; j++) //总人数不能小于要选择的人数
{
long long maxPro = LLONG_MIN;
long long minPro = LLONG_MAX;
//和j的距离不能超过d且该位置之前(包含该位置)必须至少有j-1个同学
for(int l=max(j-1,i-d); l<=i-1; l++)
{
maxPro = max(maxPro, max(maxdp[l][j-1]*array[i-1], mindp[l][j-1]*array[i-1]));
minPro = min(minPro, min(maxdp[l][j-1]*array[i-1], mindp[l][j-1]*array[i-1]));
}
maxdp[i][j] = maxPro;
mindp[i][j] = minPro;
}
}
long long res = LLONG_MIN;
for(int i=1; i<=n; i++)
{
res = max(res, maxdp[i][k]);
}
return res;
}
int main()
{
int n;
cin >> n;
vector<int> array;
for(int i=0;i<n;i++)
{
int tmp;
cin >> tmp;
array.push_back(tmp);
}
int k,d;
cin >> k >>d;
cout << process(array,n,k,d);
system("pause");
return 0;
}
#include<stdio.h> #include<vector> #include<algorithm> //#include<windows.h> using namespace std; struct node{ long Max,Min; node():Max(0),Min(0){} }; int a[100]; int main(){ int N,K,d,i,j,k; //freopen("input.txt","r",stdin); while(scanf("%d",&N)!=EOF){ for(i=0;i<N;i++) scanf("%d",&a[i]); scanf("%d%d",&K,&d); vector<vector<node> > dp(N,vector<node>(K+1)); long res=-999999999; for(i=0;i<N;i++){ dp[i][1].Max=dp[i][1].Min=a[i]; res=max(res,dp[i][1].Max); } for(i=1;i<N;i++) for(j=2;j<=min(K,i+1);j++){ for(k=1;k<=d&&k<=i;k++){ dp[i][j].Max=max(dp[i][j].Max,max(dp[i-k][j-1].Max*a[i],dp[i-k][j-1].Min*a[i])); dp[i][j].Min=min(dp[i][j].Min,min(dp[i-k][j-1].Max*a[i],dp[i-k][j-1].Min*a[i])); } res=max(res,dp[i][j].Max); } printf("%ld\n",res); } }
#python2 时间:35ms,内存:3060k 动态规划 length = input() array = [int(x) for x in raw_input().split()] k ,d =[int(x) for x in raw_input().split()] array_max=array_min=array for i in range(k-1): new_max = [-float('inf')]*length new_min = [float('inf')]*length for num in range(i+1,length): index_min = max(i,num-d) index_max = min(num+d,length) temp_max = -float('inf') temp_min = float('inf') for temp in range(index_min,num): temp_max = max(temp_max,array[num]*array_max[temp],array[num]*array_min[temp]) temp_min = min(temp_min,array[num]*array_max[temp],array[num]*array_min[temp]) new_max[num]=temp_max new_min[num]=temp_min array_max = new_max[:] array_min = new_min[:] print(max(array_max))
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { // 总人数 int n = sc.nextInt(); // 学生的能力值,第i个人对应第I个位置 int[] arr = new int[n + 1]; // 初始化 for (int i = 1; i <= n; i++) { arr[i] = sc.nextInt(); } // 选择学生数 int kk = sc.nextInt(); // 间距 int dd = sc.nextInt(); // 规划数组 long[][] f = new long[n + 1][kk + 1]; long[][] g = new long[n + 1][kk + 1]; // 初始化k=1的情况 for (int one = 1; one < n; one++) { f[one][1] = arr[one]; g[one][1] = arr[one]; } // 总人数等于1 或者大于1 if (n == 1) { System.out.println(arr[1]); } else { for (int k = 2; k <= kk; k++) { for (int one = k; one <= n; one++) { long tempmax = Long.MIN_VALUE; long tempmin = Long.MAX_VALUE; for (int left = Math.max(k - 1, one - dd); left <= one - 1; left++) { if (tempmax < Math.max(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one])) { tempmax = Math.max(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]); } if (tempmin > Math.min(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one])) { tempmin = Math.min(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]); } } f[one][k] = tempmax; g[one][k] = tempmin; } } long result = Long.MIN_VALUE; for (int one = kk; one <= n; one++) { if (result < f[one][kk]) { result = f[one][kk]; } } System.out.println(result); } } } }
比较明了的C++答案
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long> a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
int k,d;
cin>>k>>d;
vector<vector<long long>> dp_max(n+1,vector<long long>(k+1,0));
vector<vector<long long>> dp_min(n+1,vector<long long>(k+1,0));
long long res = LLONG_MIN;
for(int i=1;i<=n;++i){
dp_max[i][1] = dp_min[i][1] = a[i];
for(int j=2;j<=k&&j<=i;++j){
for(int l=1;l<=d&&i-l>=1;++l){
dp_max[i][j] = max(dp_max[i][j],max(dp_max[i-l][j-1]*a[i],dp_min[i-l][j-1]*a[i]));
dp_min[i][j] = min(dp_min[i][j],min(dp_max[i-l][j-1]*a[i],dp_min[i-l][j-1]*a[i]));
}
}
res = max(res,dp_max[i][k]);
}
cout<< res<<endl;
}
题目要求n各学生中选择k个,使这k个学生的能力值乘积最大。这是一个最优化的问题。另外,在优化过程中,提出了相邻两个学生的位置编号差不超过d的约束。
如果不用递归或者动态规划,问题很难入手,并且,限制条件d也需要对每一个进行约束,编程十分复杂
所以,解决的方法是采用动态规划(理由:1.求解的是最优化问题;2.可以分解为最优子结构)
1.对该问题的分解是关键。
从n个学生中,选择k个,可以看成是:先从n个学生里选择最后1个,然后在剩下的里选择k-1个,并且让这1个和前k-1个满足约束条件
2.数学描述
为了能够编程实现,需要归纳出其递推公式,而在写递推公式之前,首先又需要对其进行数学描述
记第k个人的位置为one,则可以用f[one][k]表示从n个人中选择k个的方案。然后,它的子问题,需要从one前面的left个人里面,选择k-1个,这里left表示k-1个人中最后一个(即第k-1个)人的位置,因此,子问题可以表示成f[left][k-1].
学生能力数组记为arr[n+1],第i个学生的能力值为arr[i]
one表示最后一个人,其取值范围为[1,n];
left表示第k-1个人所处的位置,需要和第k个人的位置差不超过d,因此
max{k-1,one-d}<=left<=one-1
在n和k定了之后,需要求解出n个学生选择k个能力值乘积的最大值。因为能力值有正有负,所以
当one对应的学生能力值为正时,
f[one][k] = max{f[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
当one对应的学生能力值为负时
f[one][k] = max{g[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
此处g[][]是存储n个选k个能力值乘积的最小值数组
遍历。因为一般看解答的多半是自己遇到问题不大会的,所以程序里面有写注释。如果大家不懂可以再问我,我回复或者再把解答写详细点。欢迎讨论。
import java.util.Scanner; public class Main_jrh_AC { public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()) { //总人数 int n = sc.nextInt(); //学生能力值数组,第i个人直接对应arr[i] int[] arr = new int[n + 1]; //初始化 for (int i = 1; i <= n; i++) {//人直接对应坐标 arr[i] = sc.nextInt(); } //选择的学生数 int kk = sc.nextInt(); //间距 int dd = sc.nextInt(); /** * 递推的时候,以f[one][k]的形式表示 * 其中:one表示最后一个人的位置,k为包括这个人,一共有k个人 * 原问题和子问题的关系:f[one][k]=max{f[left][k-1]*arr[one],g[left][k-1]*arr[one]} */ //规划数组 long[][] f = new long[n + 1][kk + 1];//人直接对应坐标,n和kk都要+1 long[][] g = new long[n + 1][kk + 1]; //初始化k=1的情况 for(int one = 1;one<=n;one++){ f[one][1] = arr[one]; g[one][1] = arr[one]; } //自底向上递推 for(int k=2;k<=kk;k++){ for(int one = k;one<=n;one++){ //求解当one和k定的时候,最大的分割点 long tempmax = Long.MIN_VALUE; long tempmin = Long.MAX_VALUE; for(int left = Math.max(k-1,one-dd);left<=one-1;left++){ if(tempmax<Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){ tempmax=Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one]); } if(tempmin>Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){ tempmin=Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one]); } } f[one][k] = tempmax; g[one][k] = tempmin; } } //n选k最大的需要从最后一个最大的位置选 long result = Long.MIN_VALUE; for(int one = kk;one<=n;one++){ if(result<f[one][kk]){ result = f[one][kk]; } } System.out.println(result); } } }
#include<iostream> using namespace std; #define MAX 100 inline long long max(long long a,long long b){return a>b?a:b;} inline long long min(long long a,long long b){return a>b?b:a;} int main() { int N,K,D; int num[MAX]={0}; long long pMax[MAX][MAX]={0}; long long pMin[MAX][MAX]={0}; cin >> N; for(int i=1;i<=N;i++) cin >> num[i]; cin>>K>>D; //思路造成我的k值在最外循环 for(int k=1;k<=K;k++) { for(int i=1;i<=N;i++) { //思路的差异在初始值上也不同 if(k==1) pMax[k][i]=pMin[k][i]=num[i]; else { for(int j=i-1;i-j<=D&&j>0;--j) { pMax[k][i]=max(pMax[k][i],max(pMax[k-1][j]*num[i],pMin[k-1][j]*num[i])); pMin[k][i]=min(pMin[k][i],min(pMax[k-1][j]*num[i],pMin[k-1][j]*num[i])); } } } } long long result = 0; //得出最后的结果 for(int i=1;i<=N;i++) result = max(result,pMax[K][i]); cout << result; return 0; }
- 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); } } }
N = int(raw_input())
A = map(int, raw_input().split())
K, D = map(int, raw_input().split())
#因为有正反所以分成两部分
dpmax = [[0]*N for i in range(K)]#列出未来将要用到的结果位置
dpmin = [[0]*N for i in range(K)]#同上
res = (1<<64)*-1#默认的最小值,后面比较需要
for n in range(N):
dpmax[0][n] = dpmin[0][n] = A[n]#就是在k=1时,取第一个值时
for k in range(1,K):
for pre in range(max(0,n-D),n):#因为有间隔,所以如果间隔大于n,可以全取,反之需从间隔部分之后开始
dpmax[k][n] = max(dpmax[k][n],max(dpmax[k-1][pre]*A[n],dpmin[k-1][pre]*A[n]))#不断与之前的进行比较获取最大
dpmin[k][n] = min(dpmin[k][n],min(dpmax[k-1][pre]*A[n],dpmin[k-1][pre]*A[n]))#不断与之前进行比较获取最小
res = max(res,dpmax[K-1][n])
#其实结果可以写成max([x for x in dpmax[K-1]]))
#因为是要在dpmax[K-1]取出最大的那个
print(max([x for x in dpmax[K-1]])))
#include <bits/stdc++.h> using namespace std; void search(vector<vector<vector<long>>>& ***, const vector<int>& a, int m_d, int i, int k, int c_d, long product, long& max) { // c_d代表与上一个被选中同学的距离 if (k == 0) { if (product > max) max = product; return; } // 与上一个同学的距离已经超过了d,不符合要求 if (c_d >= m_d) return; if (i >= a.size()) return; // 把剩下所有的同学选了也达不到人数要求,直接跳过 if (i + k > a.size()) return; // 以下的判断用于缓存数据,减少不必要的判断。不用缓存只能过80%。 if (abs(product) >= ***[i][k][c_d]) ***[i][k][c_d] = abs(product); else return; // 选中i search(***, a, m_d, i + 1, k - 1, 0, product * a[i], max); // 不选中i search(***, a, m_d, i + 1, k, product == 1 ? 0 : c_d + 1, product, max); } int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int k, d; cin >> k >> d; vector<vector<vector<long>>> ***(n, vector<vector<long>>(k + 1, vector<long>(d, 0))); long max = 0; search(***, a, d, 0, k, 0, 1, max); cout << max << endl; }
假设已经确定了k-1个人,那么只要从接下来的d个人中找到使乘积最大的人添加。反过来即得到递推思路,我们以i位置结尾,计算当前的最大乘积dp[i][k]是在j属于i-d到i之间的这部分dp[j][k-1]的基础上考虑的,也就是说一次只考虑d变化。
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int stu[] = new int[N];
for (int i = 0; i < stu.length; i++) {
stu[i] = scanner.nextInt();
}
int K = scanner.nextInt();
int D = scanner.nextInt();
getMaxProduct(N, stu, K, D);
}
/**
* 获取最大乘积
* 从n个学生中,选择k个,可以看成是:先从n个学生里选择最后1个,然后在剩下的里选择k-1个,并且让这1个和前k-1个满足约束条件
*/
private static void getMaxProduct(int N, int[] stu, int K, int D) {
// 记录以当前位置结束的取1-k个值时的最大乘积, 分正负两个情况
long fmax[][] = new long[N][K];
long fmin[][] = new long[N][K];
for (int i = 0; i < N; i++) {
// 第一个人
fmax[i][0] = stu[i];
fmin[i][0] = stu[i];
// 添加其他人
for(int k=1; k<K; k++){
// 每次只考虑添加一个人,那么范围缩小到d了!
for(int j=i-1; j>=0 && i-j<=D; j--){
// 是否替换一定是跟i和问题(乘积)有关的,并且和i-d~i范围的比较
fmax[i][k] = Math.max(fmax[i][k], Math.max(fmax[j][k-1]*stu[i], fmin[j][k-1]*stu[i]));
fmin[i][k] = Math.min(fmin[i][k], Math.min(fmax[j][k-1]*stu[i], fmin[j][k-1]*stu[i]));
}
}
}
// 取最小值(负数)只可能存在中间过程,最后结果不管正负都是取最大的那个,所以只在fmax中找
long max = fmax[0][K-1];
for (int i = 1; i < N; i++) {
max = Math.max(max, fmax[i][K-1]);
}
System.out.println(max);
}
}
#include<stdio.h> #include<stdlib.h> #include<vector> #include<iostream> using namespace std; int main() { int n,k,d,temp; int maximum=0; vector<int> a; cin>>n; for(int yy=0;yy<n;yy++) { cin>>temp; a.push_back(temp); } cin>>k; cin>>d; int dpm[k][n]; int dpn[k][n]; for(int x=0;x<k;x++) { for(int y=0;y<n;y++) { dpm[x][y]=0; dpn[x][y]=0; } } for(int xx=0;xx<n;xx++) { dpm[0][xx]=a[xx]; dpn[0][xx]=a[xx]; } for(int i=0;i<n;i++) { for(int kk=1;kk<k;kk++) { for(int j=i-1;j>max(-1,i-d-1);j--) { dpm[kk][i]=max(dpm[kk][i],max(dpm[kk-1][j]*a[i],dpn[kk-1][j]*a[i])); dpn[kk][i]=min(dpn[kk][i],min(dpm[kk-1][j]*a[i],dpn[kk-1][j]*a[i])); } } maximum=max(maximum,dpm[k-1][i]); } /*for(int xxx=k;xxx<n;xxx++) { maximum=max(maximum,dpm[k-1][xxx]); }*/ cout<<maximum<<endl; return 0; } 这个代码一直卡在50%通过率, 47 -41 -5 -10 -31 -44 -16 -3 -33 -34 -35 -44 -44 -25 -48 -16 -32 -37 -8 -33 -30 -6 -18 -26 -37 -40 -30 -50 -32 -5 -41 -32 -12 -33 -22 -14 -34 -1 -41 -45 -8 -39 -27 -23 -45 -10 -50 -34 6 3 这个例子上,正确的输出应该是5504557500 我的输出为: 2135936000