首页 > 试题广场 >

合唱团

[编程题]合唱团
  • 热度指数:105739 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?

输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。


输出描述:
输出一行表示最大的乘积。
示例1

输入

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)])


发表于 2017-08-19 23:21:33 回复(4)
思路和大家差不多,动态规划问题。dp_max[i][j],dp_min[i][j]分别表示以第i个人位结尾,选择j个人的最大乘积和最小乘积
#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;
}

发表于 2017-08-16 11:42:59 回复(4)
 import java.util.*;
public class Main{
    
    /**
    总共n个学生,从中选k个学生计算乘积
    f(i,k)代表选出k个学生,最后一个学生编号是i.. i从0到n-1
    最终在f(0,k),f(1,k),f(2,k)...f(n-1,k)中选取最大的乘积作为结果
    
    所以现在要解决的问题是怎么求f(i,k)
    假设第k-1个学生的编号为j,f(j,k-1)已知
    那么f(i,k)就可以用到f(j,k-1)的条件了。但由于学生的能力值可以为负数。
    若第i个学生的能力值为负数,要使乘积最大,则应求f(j,k-1)的最小值,记为Min.f(j,k-1);
    若第i个学生的能力值为正数,要使乘积最大,则应求f(j,k-1)的最大值,记为Max.f(j,k-1)。
    因此应该设立两个数组同时保存选取第k-1个学生后乘积的最大和最小值。
    
    values(i)代表第i个学生的能力值
    状态方程为:f(i,k) = max(f(i,k), Min.f(j,k-1)*values(i), Max.f(j,k-1)*values(i))
    
    由于i和j满足条件 i-j <= d,所以在满足条件的j中选取最大的值作为f(i,k)的值
    **/
    
    public static long getMax(long a, long b, long c){
        return Math.max(Math.max(a,b),c);
    }
    
    public static long getMin(long a, long b, long c){
        return Math.min(Math.min(a,b),c);
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int sum =1;
        int n = Integer.parseInt(scanner.nextLine());
        int[] values = new int[n];
        for(int i=0; i <n; i++){
            values[i] = Integer.parseInt(scanner.next());
        }
        int k = Integer.parseInt(scanner.next());
        int d = Integer.parseInt(scanner.next());
        
        long[][] max = new long[n][k];
        long[][] min = new long[n][k];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<k; j++){
                max[i][j] = min[i][j] = 0;
            }
        }
        
        for(int i=0; i<n; i++){
            max[i][0] = min[i][0] = values[i];
        }
        
        for(int j=1; j<k; j++){
            for(int i=0; i<n; i++){
                if(i==0) continue;
                for(int m=i-1; i-m <= d; m--){
                    if(m<0) break;
                    max[i][j] = getMax(max[i][j], max[m][j-1]*values[i], min[m][j-1]*values[i]);
                    min[i][j] = getMin(min[i][j], max[m][j-1]*values[i], min[m][j-1]*values[i]);
                }
            }
        }
        long ans = 0;
        for(int i=0; i<n; i++){
            ans = Math.max(ans, max[i][k-1] );
        }
        System.out.print(ans);
    } 
}

发表于 2018-02-15 15:31:57 回复(1)
这里借用ZhanHeng的代码,我只是打印出了过程
例如

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



具体推到就是:先找子问题的最优,并记录结果,递推
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]));
发表于 2017-08-20 10:47:07 回复(0)
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);

    }
}

发表于 2016-08-27 20:22:37 回复(4)

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;
}
发表于 2018-03-20 11:30:12 回复(1)
#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);
	}
}

发表于 2017-08-10 19:19:15 回复(1)
#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))

发表于 2017-10-21 18:41:03 回复(0)
#include <iostream>
#include <fstream>
using namespace std;

int max(int a, int b){
return a > b ? a : b;
}
void swap(int &a, int &b){
int c = a;
a = b;
b = c;
}

int main()
{
int n, k, d;
cin >> n;
int *val = new int[n + 1];
for (int i = 1; i <= n; ++i){
cin >> val[i];
}
cin >> k >> d;

//初始化
long long **arr_up = new long long*[k + 1];
long long **arr_down = new long long*[k + 1];
for (int i = 0; i < k + 1; ++i){
arr_up[i] = new long long[n + 1]();
arr_down[i] = new long long[n + 1]();
}
for (int i = 1; i < n + 1; ++i){
arr_up[1][i] = val[i];
arr_down[1][i] = val[i];
}

for (int i = 2; i <= k; ++i){ //选i个人
for (int j = i; j <= n; ++j){ //最大的位置编号
int x = max(j - d, 1);
long long sum_up = arr_up[i - 1][x] * val[j];//记录最大的数
long long sum_down = arr_down[i - 1][x] * val[j];//记录最小的数
if (sum_up < sum_down){
swap(sum_up, sum_down);
}
for (++x; x < j; ++x){
long long num = arr_up[i - 1][x] * val[j];
if (num > sum_up){
sum_up = num;
}
else if (num < sum_down){
sum_down = num;
}

num = arr_down[i - 1][x] * val[j];
if (num > sum_up){
sum_up = num;
}
else if (num < sum_down){
sum_down = num;
}
}
arr_up[i][j] = sum_up;
arr_down[i][j] = sum_down;
}
}
//获取最大乘积
long long max_sum = arr_up[k][k];
for (int i = k + 1; i <= n; ++i){
if (arr_up[k][i] > max_sum){
max_sum = arr_up[k][i];
}
}
cout << max_sum << endl;

//system("pause");
return 0;
}
发表于 2017-09-07 22:16:21 回复(0)
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);
			}

		}
	}

} 


发表于 2017-08-29 10:29:33 回复(0)

比较明了的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;
}
发表于 2017-08-10 12:04:25 回复(1)

网易_合唱团解析

1. 题目分析

题目要求n各学生中选择k个,使这k个学生的能力值乘积最大。这是一个最优化的问题。另外,在优化过程中,提出了相邻两个学生的位置编号差不超过d的约束。

如果不用递归或者动态规划,问题很难入手,并且,限制条件d也需要对每一个进行约束,编程十分复杂

所以,解决的方法是采用动态规划(理由:1.求解的是最优化问题;2.可以分解为最优子结构)

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个能力值乘积的最小值数组

3.编程实现

遍历。因为一般看解答的多半是自己遇到问题不大会的,所以程序里面有写注释。如果大家不懂可以再问我,我回复或者再把解答写详细点。欢迎讨论。

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);
        }
    }
}
编辑于 2017-09-09 23:01:06 回复(41)
我和大多数人的算法略有不同,在子问题分解上我才用从n个学生中选取1人、2人...直至k人的思路,而不是先从n个学生里选择最后1个,然后在剩下的里选择k-1个,这样的思路在编程上会造成循环上的调整和最后结果的比较不同,算法已通过样本,理解该算法最好方式是手动演算一下计算过程。



#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;
}

编辑于 2019-03-28 16:39:54 回复(0)
对于这道题我的具体思路:
  1. 看到这道题,首先最基本的想法一般是从n中抽取k个数,然后验证是否符合条件,复杂度大概是是一个非指数级可解问题
  2. 接着进一步优化,首先可以发现因为限制了相对位置d,所以问题是位置相关的,而根据乘法交换率,计算时位置无关,因此保持其位置而不是考虑排序方法更好归纳问题。因此设人的序列为ListA:a1,a2,....,an
  3. 这道题主要超变量有ListA,N.K,D从这道题跟具体的人选取与不选取有关,从头或从尾砍掉或选取一部分人,可以保持这个问题本身性质不变而只在超变量有改变,具有子问题的性质,且是最优化问题且包含最优子问题,因此考虑上贪心算法或者动态规划算法,并且先不考虑正负问题。
  4. 贪心的2个要求是最优子问题和贪心选择(在子问题迭代过程每一步都是最佳,其中不会有其它选择优于我的选择【这也是很多贪心算法的证明】)考虑ListA中对an这个人的选择入k和抛弃,前面子问题会变成k-1或者k,显而易见直接丢掉算子问题不能保证最优,因此考虑动态规划。
  5. 动态规划要求是最优子问题,重叠子问题,而动态规划又经常被大牛叫为打表算法,因此考虑打表,动态规划首先都要列出递推方程,考虑以砍尾部来划归子问题
  6. (图里公式max的第一行d应该为大写D,其应该被重置)
  7. 但是这样就会被列为三维矩阵,非常麻烦且不直观,考虑到距离d会因为选择了某人而重置为D所以考虑另外一种切分方法
  8. 但是这种方法有个问题就是listA前面的后面可能会空一大截,不一定从尾巴或头部开始切,这也符合实际问题需要。于是表大概就长下面这个样子:
  9. 这样就可以解决最大问题了,但是因为涉及正负数,负数最小的可能在下一次乘法中反成最大,所以得考虑打两个表,一个最小表一个最大表,判断哪个大取哪个。
  10. 照这个思路的具体实现跟高赞答案一样
  1. 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);         }     } }

发表于 2018-12-25 16:55:19 回复(1)

参考各位大佬的解答如:bupt渣硕,加深自己对动态规划问题的理解,附上代码和理解注释

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]])))

动态规划问题差不多一次看见,得多找一些练习一下୧(๑•̀⌄•́๑)૭

发表于 2018-09-23 14:48:59 回复(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;
}
发表于 2018-09-16 01:45:09 回复(0)

假设已经确定了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);
    }

}
发表于 2018-08-11 14:34:31 回复(0)
#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

发表于 2018-08-07 16:19:39 回复(3)
这是我提交的代码,代码正确,就是时间复杂度有点大
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为70.00%
----------------------------------------------------------------------------------------
import java.util.Scanner;
import javax.xml.soap.Detail;

/**
 *@author liujun
 *@date: 2018-5-2 Time:下午11:00:55
 *@author—Email:ljfirst@mail.ustc.edu.cn
 *@description:有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?
 *@version
1.0
 */
public class Main {

    //学生人数以及每个学生的能力值、入选学生能力值和编号
    static int student_num ;
    static long [] student_power ;
    
    //筛选最佳值、记录最佳入选能力值和最佳能力序列
    static long sum_best = 1;
    static long [] student_chosed_power ;
    static long [] student_chosed_num ;
    
    //筛选暂时值,记录入选能力值和暂时能力序列
    static long sum_temp = 1;
    static long [] student_temp_power ;
    static long [] student_temp_num ;
    
    //挑选k个学生和设置d个间距
    static int k ,d ;
    
    //动态规划开始,定义递归深度、和暂时值
    static int depth = 0;
    
    //递归传入递归深度和轮到的学生编号
    public void digui (int depth, int start){
        //边界条件判断
        if (depth > k) {
            if(sum_temp > sum_best && distance(student_temp_num)){
                sum_best = sum_temp;
                for (int e = 0; e < student_temp_power.length; e++) {
                    student_chosed_num[e] = student_temp_num[e];
                    student_chosed_power[e] = student_temp_power[e];
                }
            }
            return ;
        }
        
        for (int j = start; j < student_num; j++) {
            if(student_power[j] == 0){
                continue;
            }
            sum_temp *= student_power[j];
            student_temp_power[depth] = student_power[j];
            student_temp_num[depth] = j;
            
            digui(depth+1, j+1);
            
            sum_temp /= student_power[j];
            student_temp_power[depth]= 0;
            student_temp_num[depth] = 0;
        }
        
        return;
    }
    
    public boolean distance(long [] student_chose_num){
        for (int u = 0; u < student_chose_num.length -1; u++) {
            if(student_chose_num[u+1] - student_chose_num[u] > d){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        student_num = scan.nextInt();
        student_power = new long [student_num];
        
        //能力值赋值
        for (int i = 0; i < student_num; i++) {
            student_power[i] = scan.nextInt();
        }

        //获取k个学生和设置d个间距
        k = scan.nextInt();
        d = scan.nextInt();
        
        //记录入选学生能力值和对应序号
        student_temp_power = new long[k];
        student_temp_num = new long[k];
        student_chosed_power = new long[k];
        student_chosed_num = new long[k];
        
        k--;
        new Main().digui(0, 0);
        System.out.print(sum_best);   
    }
}

发表于 2018-05-06 15:08:38 回复(0)
一次最基本的更新过程
·「7,4,7」初始
然后·「7,4,7
           0,null,null]
然后{7,4,7
        0,4×7,null}
然后{7,4,7
        0,4×7,7×4}
然后{7,4,7
        0,4×7,7×7替换掉7×4}

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();
            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[][] fmax = new long[K+1][n+1];
            long[][] fmin = new long[K+1][n+1];
            long res = Long.MIN_VALUE;
            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 >= 1 && i-j <= d;j--) {
                        //fmax[k][i] = Math.max(fmax[k][i],fmax[k-1][j]*arr[i]);
                        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);
        }
    }
}

发表于 2018-05-02 22:14:35 回复(0)

问题信息

难度:
186条回答 72714浏览

热门推荐

通过挑战的用户

查看代码
合唱团