题解：P12234 [蓝桥杯 2023 国 Java A] 最大算式

· · 题解

题目传送门

一道贪心，思路还较好想。

进行分类讨论

  1. 当 a_i = 0 时，它不会对答案产生贡献，直接加即可。

  2. 对于两个 \ge 2 的整数 a \ge b \ge 2 ，可以证明 a \cdot b \ge a + b 。证明如下：

    a \cdot (b - 1)=a \cdot b - a , b - 1 \ge 1 a \cdot (b - 1) \ge a \ge b a \cdot b - a \ge b a \cdot b \ge a + b

    所以当 a_i \ge 2 ，将它们直接相乘一定最优。

  3. 当 a_i = 1 ,对于每一段连续的 1 ，容易证明尽量将 3 个 1 加成一个 3 是最优的，例如有 6 个连续的 1 ， (1 + 1 + 1) \cdot (1 + 1 + 1)=9 一定是最优解。所以用 cnt 记录每一个连续的1有多少个， k=cnt \bmod 3 表示每 3 个一组分完后还剩几个 1 。

    • 当 k = 1 ，最优的方法是加到连续 a_i = 1 段的左右两侧中较小的那个数。如果 cnt > 3 且左右两个数 > 3 ，那么将1加到任意一个 3 （ 3 个 1 分成一组相加）上。
    • 当 k = 2 ，需要考虑到下面的情况： 
      2 1 (若干个3) 1 2

      此时若将剩下的两个 1 分为一组相加，得到 ( 1 + 1 ) \cdot 2 \cdot 2 = 8，但当分别与一个 2 分为一组，可得 (2+1) \cdot (2+1)=9>8 ，此时达到最优，其余情况就将两个1分为一组相加得到 1+1=2 。

综上所述，我们就可以贪心的写出代码。

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],m,s[100005],ans=1,mod=1e9+7,cnt;//s为按上述方法分组后的数组，m为其上限，ans统计答案。
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    s[0]=1e9;//防止左右判断大小时将s[0]=0判断进去了
    for(int i=1;i<=n;i++)
    {
        if(!a[i]) continue;//a[i]=0跳过
        else if(a[i]==1) cnt++;//cnt记录1的个数
        else
        {
            if(!cnt) s[++m]=a[i];
            else if(cnt==1)
            {
                if(s[m]<=a[i]) s[m]++;
                else a[i]++;
                s[++m]=a[i];
            }//cnt=1时比较左右的大小
            else if(cnt==2)
            {
                if(s[m]==2&&a[i]==2) s[m]=s[++m]=3;
                else s[++m]=2,s[++m]=a[i];
            }//特判2 1 1 2的情况
            else
            {
                int k=cnt%3;
                if(k==2)
                {
                    if(s[m]==2&&a[i]==2) s[m]=a[i]=3;
                    else s[++m]=2;
                }
                else if(k==1)
                {
                    if(s[m]==2) s[m]++;
                    else if(a[i]==2) a[i]++;
                    else
                    {
                        s[++m]=4;
                        cnt-=4;
                    }
                }//k=1和k=2思路同上
                for(int j=1;j<=cnt/3;j++) s[++m]=3;
                s[++m]=a[i];
            }
            cnt=0;
        }
    }
    if(cnt==1) s[m]++;
    else if(cnt==2) s[++m]=2;
    else if(cnt>2)
    {
        int k=cnt%3;
        if(k==1)
        {
            if(s[m]==2) s[m]++;
            else
            {
                s[++m]=4;
                cnt-=4;
            }
        }
        else if(k==2)
        {
            s[++m]=2;
            cnt-=2;
        }
        for(int i=1;i<=cnt/3;i++) s[++m]=3;
    }
  //防止还有末尾的1
    for(int i=1;i<=m;i++)
    {
        ans=ans*s[i]%mod;
    }//统计答案
  //不开long long见祖宗
    cout<<ans;
    return 0;
}