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

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

进行分类讨论

当 $a_i = 0$ 时，它不会对答案产生贡献，直接加即可。
对于两个 $\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$ ，将它们直接相乘一定最优。
当 $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$ ，需要考虑到下面的情况：

CPP

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

。

当 $k=0$ ，表示 $cnt$ 是 $3$ 的倍数，此时已经达到最优。

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

CPP

#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;
}

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

文章操作

相关推荐

评论

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