自动搬运

查看原文

来自洛谷，原作者为

	yanmingqian 莫等痛时才知痛

搬运于2025-08-24 23:13:53，当前版本为作者最后更新于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);
    }
}