合唱团

问题描述:

有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?

dpi表示 依次选好第i个学生时 他在队伍里排第j名能力值乘积最大为多少 应该是i>=j
dpi = arr[i] * max(dpi-1);
边界条件 dp0=1;
但是因为每个学生的能力有正有负,所以如果arr[i]为负值,那么dpi = arr[i] * min(dpi-1);
我们可以
用dp1i表示依次选好第i个学生时 他在队伍里排第j名能力值乘积最大为多少
用dp2i表示依次选好第i个学生时 他在队伍里排第j名能力值乘积最小为多少

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long int 
const ll maxn = 55;
ll arr[maxn];
ll dp1[maxn][maxn];        //存最大值 
ll dp2[maxn][maxn];        //存最小值 
int main()
{
    ll n;                                //n个学生 
    while(cin>>n)
    {
        for(ll i=1;i<=n;++i)
        {
            cin>>arr[i];                //每个学生的能力值有正有负 
        }
        ll k,d;    //k个学生,编号差值不超过d 
        cin>>k>>d;
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        for(ll i=0;i<=n;++i)
        {
            dp1[0][i]=1;
            dp2[0][i]=1; 
        }
        
        for(ll i=1;i<=k;++i)
        {
            for(ll j=1;j<=n;++j)
            {
                if(i>j) continue;                //选好了I个人,他不可能在原来的队伍 
                ll num1 = -1<<30;
                ll num2 = 1<<30;
                for(int m=1;m<=d;++m)
                {
                    if(j-m<0) break;
                    num1=max(num1,dp1[i-1][j-m]);
                    num2=min(num2,dp2[i-1][j-m]);
                }
                dp1[i][j] =max(num2 * arr[j], num1 * arr[j]);
                dp2[i][j] =min(num2 * arr[j], num1 * arr[j]); 
            }
        }
        ll ans = -1<<30;
//        for(int i=0;i<=k;++i)
//        {
//            for(int j=1;j<=n;++j)
//            {
//                cout<<dp1[i][j]<<" ";
//            }
//            cout<<endl;
//        } 
        for(ll i=k;i<=n;++i)
        {
            ans = max(ans,dp1[k][i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
Last modification:September 19th, 2019 at 12:12 am
如果觉得我的文章对你有用,请随意赞赏