00:00/00:00

Description

Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳,打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N ≤ 100,000) 只,按顺序串在树枝上。为了方便,我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同,贝壳 i 的大小为 si(1 ≤ si ≤10,000)。变柠檬的魔法要求,Flute 每次从树枝一端取下一小段连续的贝壳,并选择一种贝壳的大小 s0。如果 这一小段贝壳中 大小为 s0 的贝壳有 t 只,那么魔法可以把这一小段贝壳变成 s0*t^2 只柠檬。Flute 可以取任意多次贝壳,直到树枝上的贝壳被全部取完。各个小段中,Flute 选择的贝壳大小 s0 可以不同。而最终 Flute 得到的柠檬数,就是所有小段柠檬数的总和。Flute 想知道,它最多能用这一串贝壳变出多少柠檬。请你帮忙解决这个问题。

Input

第 1 行:一个整数,表示 N。
第 2 .. N + 1 行:每行一个整数,第 i + 1 行表示 si。

Output

仅一个整数,表示 Flute 最多能得到的柠檬数。

分析:

我们发现,显然题目转化为序列分割问题,而且每个分出来的序列首尾肯定相同(否则去掉之后这一段贡献不变,产生了新的段使得最终答案更大),所以我们得到普及组dp:令f[i]表示前i位的最大价值,那么:f[i]=f[j-1]+a[j]*(c[i]-c[j]+1)^2c[i]代表前i个数里a[i]出现的次数 。
然后我们发现直接这么做是n^2的复杂度,会挂,我们考虑优化…
我们发现后面那个平方随着i的上升它是单调不降的,所以我们对于每个权值开个单调栈保存当前最优解的j,然后用栈顶更新即可。
每次要入栈之前,如果栈底第二个元素f值已经大于栈顶了,说明栈顶没用了,就弹出直到栈顶大于栈顶第二个元素的贡献为止。但是可能出现后面的超过栈顶但是第二个元素没超过的情况,所以我们在每次入栈之前,要先判断第二个元素和第一个元素超过当前i的时间,如果第二个超过时间比第一个早,弹出栈顶直到情况改变为止。

代码:

#include <bits/stdc++.h>
#define LL long long 
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; register char c=getchar(); register bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL f[100010];
int c[100010], cnt[10010], col[100010], n;
vector<int> st[100010];
LL across(int x, int y) { return f[x - 1] + (LL)col[x] * y * y; }
int fron(int x, int y)
{
    int l = 1, r = n, pos = r + 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (across(x, mid - c[x] + 1) >= across(y, mid - c[y] + 1)) pos = mid,r = mid - 1;
        else l = mid + 1;
    }
    return pos;
}
int main()
{
    read(n);
    for (int i = 1, x; i <= n; i++)
    {
        read(x);
        col[i] = x;c[i] = ++cnt[x];
        while (st[x].size() >= 2 && fron(st[x][st[x].size() - 2], st[x][st[x].size() - 1]) <= fron(st[x][st[x].size() - 1], i)) st[x].pop_back();
        st[x].push_back(i);
        while (st[x].size() >= 2 && fron(st[x][st[x].size() - 2], st[x][st[x].size() - 1]) <= c[i]) st[x].pop_back();
        f[i] = across(st[x][st[x].size() - 1], c[i] - c[st[x][st[x].size() - 1]] + 1);
    }
    printf("%lld", f[n]);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注