【题目描述】：有N个整数从左往右排成一行，下标从0至N-1。你要从这N个整数中挑选出K个整数，使得这K个整数的乘积最大。但是有个前提条件：把你选中的那K个数的下标从小到大排序后，相邻的两个下标的差的绝对值不能超过给定的参数MaxDist。
输入格式：
多组测试数据。
    第一行，一个整数R，表示有R组测试数据。
    每组测试数据格式：
       第一行，三个整数，N，K，MaxDist。1<=N<=50，1<=K<=10， 1<=MaxDist<=50。
       第二行，N个整数，每个整数的范围是-50至50。
输出格式：
共R行，每行一个整数。
输入样例：
5
3 2 1
7 4 7
3 2 50
7 4 7
6 3 3
-3 -5 -8 -9 -1 -2
10 2 2
3 0 -2 10 0 0 3 -8 0 2
48 1 7
27 42 1 31 -23 19 25 -32 46 -3 -46 5 -26 45 8 -48 -15 -20 43 15 39 -50 29 25 -14 -1 -43 21 38 32 -23 9 49 9 -7 49 20 -19 47 -33 1 18 23 -46 5 -28 5 47
输出样例：
28
49
-10
0
49

我是一名刚学习编程的学生，想请一位老师帮忙答疑。不知道有没有那位老师帮帮我！！！

好象是组合问题
N个中选K个，选出一组时判断乘积最大和下标条件，符合则为所求。

主要是觉得没办法枚举。能否说的详细点。

话说,50的10次方,输出整数会超过unsigned int型么~
不知道用dfs能不能实现~

可以试试在区间[0,n]内选最大值,然后n不断扩大,再调整最大值~
感觉这是个区间dp,可以看看区间dp的相关资料~

记录选下标0时最大值是多少,
记录选下标1时最大值是多少,
记录选下标2时最大值是多少,
记录选下标n时最大值是多少,
区间为n的最大值有MaxDist种选择~
也就是从[n-MaxDist,n]里面选一个最大的~

具体点就是要开一个二维数组(一维或者可以,但要试试才知道,类似于0-1背包问题)
取下标n取一个数的最大值是多少,
取下标n取两个数的最大值是多少,
取下标n取k个数的最大值是多少

取下标n取k个数的最大值等于取区间[n-MaxDist,n]取k-1个数的最大值加上某值的最大值~

最后看看选哪个下标的值最大就是那个数了~

[此贴子已经被作者于2018-1-7 23:53编辑过]

下班时无聊随手瞎写的，对不对你自己检查一下

#include <stdio.h>
#include <limits.h>

long long foo( unsigned n, unsigned k, unsigned maxdist, const int a[] )
{
#define __MAX(a,b)  (((a) > (b)) ? (a) : (b))
#define __MIN(a,b)  (((a) < (b)) ? (a) : (b))

    long long retval = LLONG_MIN;

    long long buf[50][10][2];
    for( unsigned i=0; i!=n; ++i )
    {
        buf[i][0][0] = a[i];
        buf[i][0][1] = a[i];

        for( unsigned j=1; j!=__MIN(i+1,k); ++j )
        {
            long long minval = LLONG_MAX;
            long long maxval = LLONG_MIN;
            for( unsigned p=__MAX(j-1,i>maxdist?i-maxdist:0); p!=i; ++p )
            {
                minval = __MIN( minval, __MIN(buf[p][j-1][0]*a[i],buf[p][j-1][1]*a[i]) );
                maxval = __MAX( maxval, __MAX(buf[p][j-1][0]*a[i],buf[p][j-1][1]*a[i]) );
            }
            buf[i][j][0] = minval;
            buf[i][j][1] = maxval;
        }

        if( i+1 >= k )
            retval = __MAX( retval, buf[i][k-1][1] );
    }

    return retval;

#undef __MAX
#undef __MIN
}

#include <assert.h>

int main( void )
{
    {
        const int a[] = { 7, 4, 7 };
        long long r = foo( 3, 2, 1, a );
        assert( r == 28 );
        printf( "%lld\n", r );
    }
    {
        const int a[] = { 7, 4, 7 };
        long long r = foo( 3, 2, 50, a );
        assert( r == 49 );
        printf( "%lld\n", r );
    }
    {
        const int a[] = { -3, -5, -8, -9, -1, -2 };
        long long r = foo( 6, 3, 3, a );
        assert( r == -10 );
        printf( "%lld\n", r );
    }
    {
        const int a[] = { 3, 0, -2, 10, 0, 0, 3, -8, 0, 2 };
        long long r = foo( 10, 2, 2, a );
        assert( r == 0 );
        printf( "%lld\n", r );
    }
    {
        const int a[] = { 27, 42, 1, 31, -23, 19, 25, -32, 46, -3, -46, 5, -26, 45, 8, -48, -15, -20, 43, 15, 39, -50, 29, 25, -14, -1, -43, 21, 38, 32, -23, 9, 49, 9, -7, 49, 20, -19, 47, -33, 1, 18, 23, -46, 5, -28, 5, 47 };
        long long r = foo( 48, 1, 7, a );
        assert( r == 49 );
        printf( "%lld\n", r );
    }

    return 0;
}

收到的鲜花

• 九转星河 于 2018-01-08 17:17 送鲜花  20朵   附言：就一个字:好 ~

r版厉害

我就说了思路,而r版给出代码并且我看了验证我的思路是正确的,但能把细节写出来这点相比之下我还是要用功的,而且不但给出最大值还给出最小值这样更好理解问题的本质真的很不错,值得收藏~

r版功力深厚,值得学习,不过我却还思考到一个优化的算法:

具体算法框架还是不变,就是在寻找区间最大值最小值那里可以优化一下
具体就是[n,n+MaxDist]的极值和[n+1,n+MaxDist+1]极值之间的关系可以递推,
所以预先开多个数组保存[0,MaxDist]到[N-MaxDist,N]的极值就可以了~

[此贴子已经被作者于2018-1-8 18:44编辑过]

非常感谢两位版主！谢谢您们！