东华大学2020年程序设计竞赛（同步赛）G Gaming with Mia（动态规划）

题意

有 $n$ 个数，每个数取值范围为 $[-1,1]$ 。现在要在两两数之间插入 $+$ 和 $\times$ 两种运算符，使得运算结果最大化，求最大化的结果。
其中， $n\leq 10^5$ 。

分析

这里提供一种非主流做法。
最终的形式肯定是一块块乘积相加的形式，于是我们考虑 $dp$ 。
令 $f_i$ 表示来到 $i$ 时的最大值。
那么 $f_i=max\{f_j+val_{j+1,i}\}$ 。其中， $val_{x,y}$ 指的是 $[x,y]$ 这段区间每个数的乘积。
由于 $val_{j+1,i}$ 的取值只有 $-1,0,1$ 三种情况，我们分情况考虑：

乘积为 $0$ ，也就是这段区间中包含了至少 $1$ 个 $0$ ，那这段区间一定包含了离 $i$ 最近的 $0$ ，不妨记这个位置为 $p$ ，那么 $f_i=max\{f_j\}(j<p)$
乘积不为 $0$ ，那么决策点一定是在 $[p+1,i-1]$ 中进行选择。
如果 $a_i=1$ ，那么最优的方式肯定是从 $f_{i-1}$ 转移过来，即 $f_i=f_{i-1}+1$ 。
如果 $a_i=-1$ ，那么可以有两种转移方式：
第一种是 $f_i=f_{i-1}-1$ 。也就是直接从 $f_{i-1}$ 转移过来。
第二种是找到上一个 $-1$ 的位置 $las$ ，那么 $[las,i]$ 这段区间的乘积为 $1$ ， $f_i=f_{las-1}+1$ 。

可以发现上面的转移是可以保证答案最优的。
由于 $p$ 和 $las$ 是递增的，复杂度可以做到 $O(n)$ 。（当然用线段树也可以）

代码如下

#include <bits/stdc++.h>
using namespace std;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
const int N = 100005;
int a[N], f[N], val;
int main(){
    int i, j, n, m, T, p, las;
    T = read();
    while(T--){
        n = read();
        for(i = 1; i <= n; i++) f[i] = 0, a[i] = read();
        p = las = val = 0;
        for(i = 1; i <= n; i++){
            if(a[i] == 0){
                while(p < i) val = max(val, f[++p]);
            }
            f[i] = f[i - 1] + a[i];
            if(p > 0) f[i] = max(f[i], val);
            if(a[i] == -1){
                if(las > p) f[i] = max(f[i], f[las - 1] + 1);
                las = i;
            }
        }
        printf("%d\n", f[n]);
    }
    return 0;
}