Codeforces 1660D 最大子段积

题意：

给一个长度为$n$的数组$(n\le 100000)$，对任意$i\in [1,n]$，有 a i ∈ { − 2 , − 1 , 0 , 1 , 2 } a_{i}\in\{-2,-1,0,1,2\} ai​∈{−2,−1,0,1,2}，可以删去数组的前任意多个和后任意多个。若要使删完之后的数组的元素积最大，求前面删多少，后面删多少

方法：

这是一个求最大子段积的问题，我们先抛开一切其他问题，仅仅讨论一个数组的最大子段积如何求，和最大子段和类似，设$dp[i]$为以$i$为结尾的最大子段积是多少，那么转移应该是从$dp[i-1]$转移来的，对于最大子段和，有$dp[i]=max(dp[i-1]+a[i],a[i])$，同样，我们每次对$a[i]$的决策也仅有两种，加入前面的子段，或者单独成段，但乘法存在负负得正，可能$a[i]<0$，而前面的最小子段和$\times a[i]$可能大于最大子段和$\times a[i]$，因此，求最大子段积需要维护两个量，一个是最大子段积，一个是最小子段积，令他们分别是$f[i],g[i]$，有

$$f[i]=max(f[i-1]\ast a[i],a[i,g[i-1]\ast a[i])$$

$$g[i]=min(g[i-1]\ast a[i],a[i],f[i-1]\ast a[i])$$

对于题目的范围，最大的子段积能达到$2^{100000}$，爆$longlong$，而这里只存在$-2,-1,0,1,2$，所以可以封装一个结构体，来表示$a{2}^b$，重载运算符来计算。

并且题目问的是前面需要删多少个，那么可以多维护两个$ftot[i],gtot[i]$，来表示以$i$结尾的子段长度是多少

#include
#define ll long long
using namespace std;

struct newint
{
    int a,b;
    void trans(int tmp)
    {
        a=(tmp>=0);
        tmp=abs(tmp);
        if(tmp==2) b=1;
        else if(tmp==1) b=0;
        else b=-1;
    }
    void solve(){if(b==-1) a=1;}
    void operator=(const newint& x)
    {
        a=x.a; b=x.b;
        solve();
    }
    bool operator==(const newint& x) const
    {
        return a==x.a&&b==x.b;
    }
    bool operator<(const newint& x) const
    {
        if(a>x.a) return false;
        else if(a<x.a) return true;
        // printf("b=%d,x.b=%d\n",b,x.b);
        if(a==0) return b>x.b;
        return b<x.b;
    }
    bool operator!=(const newint& x) const
    {
        return !(*this==x);
    }
    bool operator>(const newint& x) const
    {
        return *this!=x&&!(*this<x);
    }
    newint operator*(const newint& x) const
    {
        newint ret;
        ret.a=a^x.a^1;
        if(b==-1||x.b==-1) ret.b=-1;
        else ret.b=b+x.b;
        ret.solve();
        return ret;
    }
};

int n,ftot[200005],gtot[200005];
newint a[200005],f[200005],g[200005];

void work()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int tmp; scanf("%d",&tmp);
        a[i].trans(tmp);
    }
    newint max1={-1,-1};
    for(int i=1;i<=n;i++)
    {
        if(f[i-1]*a[i]>a[i])
        {
            f[i]=f[i-1]*a[i];
            ftot[i]=ftot[i-1]+1;
        }
        else f[i]=a[i],ftot[i]=1;
        if(a[i]*g[i-1]>f[i]) f[i]=a[i]*g[i-1],ftot[i]=gtot[i-1]+1;
        if(g[i-1]*a[i]<a[i])
        {
            g[i]=g[i-1]*a[i];
            gtot[i]=gtot[i-1]+1;
        }
        else g[i]=a[i],gtot[i]=1;
        if(a[i]*f[i-1]<g[i]) g[i]=a[i]*f[i-1],gtot[i]=ftot[i-1]+1;
        max1=max(max1,f[i]);
    }
    if(max1<(newint){1,0}||max1==(newint){1,0})
    {
        printf("%d %d\n",0,n);
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]==max1)
        {
            printf("%d %d\n",i-ftot[i],n-i);
            return;
        }
    }
}

int main()
{
    f[0].trans(1); g[0].trans(1);
    int t; cin>>t;
    while(t--) work();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104