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

yanmingqian · 2025-04-20 22:49:20 · 题解

看起来很像动态规划，动态规划或许也能做，但是实际上可以贪心。

正常人都知道通常来说乘是比加更优的。但是样例就能告诉我们并不完全是这样。因为 1 和 0 的存在，这一点不完全正确。0 好说，加上也对答案没有贡献，输入的时候直接丢掉就行。考虑 1 应该怎么办。

假设 1 前面是一个数 a，后面是一个数 b。贪心考虑，应该把 1 加到 a 和 b 中更小的那个上面。因为 (a+1)\times b=ab+b，a\times(b+1)=ab+a，所以加到更小的上面增加得更多。

但是前面说的 a 和 b 不一定是紧贴着当前的 1 的，可能中间隔了连续的 1。因此我们要记录一下上一个不是 1 的地方，每次遍历到 a_i=1 时将其与 a_{i+1} 进行比较。同时我们不得不考虑一个特殊情况，加到 2 上是可能比加到 1 上更优的，除非有连续三个或以上的 1。我们可以通过下面的一组样例理解：

7
1 1 2 1 1 1 1

正确答案应该是 18=(1+1)\times(2+1)\times(1+1+1)，但是如果把第四个位置上的 1 放到了后面，算出来就会变成 16。因此我们需要考虑这一点。

根据这个思路我们就能写出代码了。

#include<iostream>
using namespace std;
const int mod=1e9+7;
long long a[100010];
int main(){
    int n,m=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x){
            a[++m]=x;  //把0排掉
        }
    }
    int last=0;
    for(int i=1;i<=m;i++){
        if(a[i]==1){
            if(!last){
                if(i<m){  //边界
                    a[i+1]++;
                }
            } 
            else{
                if(i<m){  //边界
                    if(a[last]<=a[i+1]||a[last]==2){  //加到更小的上面，注意判断2的情况
                        a[last]++;
                    }
                    else{
                        a[i+1]++;
                    }
                }
                else{
                    a[last]++;
                }
            }
        }
        else if(a[i]>1){
            last=i;
        } 
    }
    long long ans=1;
    for(int i=1;i<=m;i++){
        ans=(ans*a[i])%mod;
    }
    cout<<ans;
    return 0;
}

import java.util.Scanner;
public class Main {
    private static final int mod = (int) 1e9 + 7;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[100010];
        int m = 0;
        for (int i = 1; i <= n; i++) {
            int x = scanner.nextInt();
            if (x != 0) {
                a[++m] = x;
            }
        }
        int last = 0;
        for (int i = 1; i <= m; i++) {
            if (a[i] == 1) {
                if (last == 0) {
                    if (i < m) {
                        a[i + 1]++;
                    }
                } else {
                    if (i < m) {
                        if (a[last] <= a[i + 1] || a[last] == 2) {
                            a[last]++;
                        } else {
                            a[i + 1]++;
                        }
                    } else {
                        a[last]++;
                    }
                }
            } else if (a[i] > 1) {
                last = i;
            }
        }
        long ans = 1;
        for (int i = 1; i <= m; i++) {
            ans = (ans * a[i]) % mod;
        }
        System.out.println(ans);
    }
}