最大乘积

最大乘积

时间： 1ms        内存：128M

描述：

对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？

输入：

第一行一个数 代表数据组数
每组数据共两行
第一行两个正整数n、m， n,m<=20
第二行给出n个整数，其中每个数的绝对值小于4

输出：

每组数据输出1行，为最大的乘积

示例输入：

1
5 5
1 2 3 4 2

示例输出：

48

提示：

参考答案（内存最优[1116]）：

#include<stdio.h>
int n,m,a[25],b[25];
long long ans;
void dfs(int idx,int num) {
    if (num == m+1) {
        long long  res=1;
        for (int i=1;i<num;i++)
            res *= b[ a[i] ]; 
        if(res>ans) ans=res;
        return;
    }
    for (int i=idx;i<=n;i++) {
        a[num]=i;
        dfs(i+1,num+1);
    }
}
int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) 
            scanf("%d",&b[i]);
        ans=1ll<<63;
        dfs(1,1);
        printf("%lld\n",ans);
    }
    return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[25];
int main() {
	int T,n,m;
	scanf("%d",&T);
	while(T--) {
		long long ans = 1;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) 
			scanf("%d",&a[i]);	
		sort(a+1,a+n+1);
        if(m&1) {
            if(a[n]<0) {
                for(int i=n-m+1;i<=n;i++)
                    ans*=a[i];
                m=0;
            }
            else
                ans*=a[n],n--,m--;
        }
		int l=1;
		while(m) {
			if(a[l]*a[l+1] >= a[n]*a[n-1])
				ans*=a[l]*a[l+1],l+=2;
			else 
				ans*=a[n]*a[n-1],n-=2;
			m-=2;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。