CF1696H Maximum Product?

· · 题解

很难理解为什么这题能 3500 以及为什么放 H，感觉比 G 简单到不知道哪里去了。

先考虑给定一个序列，怎么求出从中选出 m 个数的最大乘积。

首先有一个很自然的想法是取绝对值最大的 m 个数，这样乘积的绝对值也会比较大。

但是有可能出现乘积为负数的情况，此时可以进行调整，一定为以下三种情况之一：

对两种情况取 \max 即可。

但是这题在 \max 外面套了 \sum，这导致不容易直接进行 dp。

考虑先进行一遍 O(n^2) 的 dp 算出调整前的答案，然后再对被错误计算的部分进行调整。

对于 B 中所有数都是负数且 m 是奇数的情况，我们只需要对所有负数做两遍类似的 dp 即可完成调整。

剩余的情况就需要进行一些讨论。

设 i_1,i_2 分别表示调整前的方案中已选的绝对值最小的非负数和负数。

设 j_1,j_2 分别表示调整前的方案中未选的绝对值最大的非负数和负数。

上面的已选和未选都是针对 B 内的数而言，B 外的数一律不进行考虑。

需要注意的是，i_1,i_2,j_1,j_2 中的某些可能是不存在的。

这里只考虑四个数都存在的情况，其它的情况是更弱的，但需要注意细节处理上的问题。

我们从绝对值比 i_1 大的非负数以及绝对值比 i_2 大的负数中选出 m-2 作为调整前的方案。

在这种情况下如果需要进行调整，那么必定满足这 m-2 个数的乘积为非负数，这是因为 i_1 和 i_2 的乘积为负数，而调整后的结果一定为负数。

设这 m-2 个数的所有需要调整的方案的权值和为 w。

在第一遍计算中，我们把这些方案的权值和算作了 w\times i_1\times i_2，但实际上，这些方案的权值和应当为 w\times\max(i_1\times j_1,i_2\times j_2)，我们只需补上这个差值即可。

但直接枚举这四个数是 O(n^4) 的。我们可以考虑把 \max 拆开来，按照两种调整方式的优劣关系分类计算。这里只讨论 i_1\times i_2\ge i_2\times j_2 的情况，另一种的处理方法是类似的。

只需要枚举 i_1,i_2,j_1，满足条件的 j_2 是一段后缀，直接双指针就可以做到 O(n^3)。

这里需要注意一些细节：B 中可能存在绝对值比 j_1 小的非负数以及绝对值比 j_2 小的负数，但它们的存在并不会影响 B 的权值，只需乘上一个 2 的幂次即可。

于是就做完了，嘴巴起来很快，写起来很吃屎。实际上这道题有很多不同的但是等价的做法，代码难度差别可能比较大，这篇题解写的是我在写代码的过程中总结出来的一种相对简洁的讨论方法。可惜改变不了屑题的本质，还是有很多细节。可能这就是本题难点吧。

时间复杂度 O(n^3)。

目前是 CF 上最快解。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 605
#define MOD 1000000007
int n,m,t,ans,a[N],a1[N],a2[N],b1[N],b2[N],dp1[N],pw[N*2],dp[N][2],tmp[N][2];
bool cmp(int x,int y) {return x>y;}
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int main()
{
    scanf("%d %d",&n,&m);pw[0]=1;
    for(int i=1;i<=n*2;++i) pw[i]=add(pw[i-1],pw[i-1]);
    for(int i=1,x;i<=n;++i)
    {scanf("%d",&x);if(x<0) a2[++a2[0]]=-x;else a1[++a1[0]]=x;}
    sort(a1+1,a1+a1[0]+1,cmp);sort(a2+1,a2+a2[0]+1,cmp);t=1;
    for(int i=1;i<=a1[0];++i)
    {
        while(t<=a2[0] && a1[i]<a2[t]) a[b2[t]=++a[0]]=MOD-a2[t],++t;
        a[b1[i]=++a[0]]=a1[i];
    }while(t<=a2[0]) a[b2[t]=++a[0]]=MOD-a2[t],++t;dp1[0]=1;
    for(int i=1;i<=n;++i)
    {
        W(dp1[m],dp1[m]);
        for(int j=min(m,i-1);j>=0;--j) W(dp1[j+1],1ll*dp1[j]*a[i]%MOD);
    }ans=dp1[m];
    if(m&1)
    {
        for(int i=0;i<=m;++i) dp1[i]=0;dp1[0]=1;
        for(int i=1;i<=a2[0];++i)
        {
            W(dp1[m],dp1[m]);
            for(int j=min(m,i)-1;j>=0;--j) W(dp1[j+1],1ll*dp1[j]*a2[i]%MOD);
        }W(ans,dp1[m]);for(int i=0;i<=m;++i) dp1[i]=0;dp1[0]=1;
        for(int i=a2[0];i;--i)
        {
            W(dp1[m],dp1[m]);
            for(int j=min(m,a2[0]-i+1)-1;j>=0;--j) W(dp1[j+1],1ll*dp1[j]*a2[i]%MOD);
        }W(ans,MOD-dp1[m]);for(int i=0;i<=m;++i) dp1[i]=0;dp1[0]=1;t=0;
        for(int i=1,w;i<=a2[0];++i)
        {
            w=dp1[m-1];while(t<=a1[0] && b1[t]<=b2[i]) ++t;
            if(w) for(int j=t;j<=a1[0];++j)
                W(ans,1ll*(a1[j]+a2[i])*w%MOD*pw[a1[0]+a2[0]-i-j]%MOD);
            for(int j=min(m,i)-1;j>=0;--j) W(dp1[j+1],1ll*dp1[j]*a2[i]%MOD);
        }
    }dp[0][0]=1;
    if(m>1) for(int i=1,t1,t2,w;i<=a1[0];++i)
    {
        for(int j=0;j<=min(m,i-1);++j)
            tmp[j][0]=dp[j][0],tmp[j][1]=dp[j][1];t1=t2=0;
        for(int j=1;j<=a2[0];++j)
        {
            w=dp[m-2][0];
            if(w)
            {
                while(t1<=a1[0] && b1[t1]<=max(b1[i],b2[j])) ++t1;
                while(t2<=a2[0] && b2[t2]<=max(b1[i],b2[j])) ++t2;t=t2;
                for(int k=t1;k<=a1[0];++k)
                {
                    while(t<=a2[0] && 1ll*a1[i]*a1[k]<1ll*a2[j]*a2[t]) ++t;
                    W(ans,1ll*a1[i]*(a1[k]+a2[j])%MOD*w%MOD*pw[a1[0]+a2[0]-k-t+1]%MOD);
                }t=t1;
                for(int k=t2;k<=a2[0];++k)
                {
                    while(t<=a1[0] && 1ll*a1[i]*a1[t]>=1ll*a2[j]*a2[k]) ++t;
                    W(ans,1ll*a2[j]*(a1[i]+a2[k])%MOD*w%MOD*pw[a1[0]+a2[0]-k-t+1]%MOD);
                }
            }
            for(int k=min(m,i+j-1)-1;k>=0;--k)
            {
                W(dp[k+1][1],1ll*dp[k][0]*a2[j]%MOD);
                W(dp[k+1][0],1ll*dp[k][1]*a2[j]%MOD);
            }
        }for(int j=0;j<=m;++j) dp[j][0]=tmp[j][0],dp[j][1]=tmp[j][1];
        for(int j=min(m,i)-1;j>=0;--j)
            W(dp[j+1][0],1ll*dp[j][0]*a1[i]%MOD),W(dp[j+1][1],1ll*dp[j][1]*a1[i]%MOD);
    }printf("%d\n",ans);return 0;
}