$BearandBowling$Bear and Bowling

题意与 这道题目 大致相同, 唯一不同的是所选序列可以在原序列中不连续, 即子序列 .

$最初想法$最初想法

设 $F[i,j]$F[i,j] 为第 $i$i 个数作为选出的 $j$j 个数中最后一个数时的最优值,
则 $F[i,1]=A\left[1\right],F[0,0]=0$F[i,1]=A[1],F[0,0]=0
$F[i,j]=\underset{}{\max }\left(F\right[k,j-1]+A[i]\ast j)$F[i,j]=k∈[1,i)max​(F[k,j−1]+A[i]∗j)

时间复杂度 $O\left(N^3\right)$O(N3), 空间复杂度 $O\left(N^2\right)$O(N2), 无法 $AC$AC,

设 $F[i,j]$F[i,j] 为前 $i$i 个数, 选出 $j$j 个数的最优值,
则 $F[0,0]=0$F[0,0]=0

$F[i,j]=\max \left\{F\right[i-1,j],F[i-1,j-1]+j\ast A[i\left]\right\}$F[i,j]=max{F[i−1,j],F[i−1,j−1]+j∗A[i]}

时间复杂度 $O\left(N^2\right)$O(N2), 开滚动数组 空间复杂度 $O\left(N\right)$O(N), 仍无法 $AC$AC .

$正解部分$正解部分

首先要知道一个结论:

对上面的第二个状态转移方程的每个 $F[i,j]$F[i,j], 都存在 $1\le K\le i$1≤K≤i,

• $0\le j\&lt;K$0≤j<K 全部由 $F[i,j-1]$F[i,j−1] 转移而来, 在滚动数组中相当于不动 .
• $K\le j\le i$K≤j≤i 全部由 $F[i-1,j-1]+j\ast A\left[i\right]$F[i−1,j−1]+j∗A[i] 转移而来 .

称 $K$K 为 分界点, 分界点左边称 左区间, 右边 为 右区间 .

至于证明… , 可以看一下 这位 的博客.

• 二分找到 分界点,
  具体地说:
  若 $F\left[mid\right]\&lt;F\left[mid\right]+mid\ast A\left[i\right]$F[mid]<F[mid]+mid∗A[i],
  说明 $mid$mid 处于右区间, $K$K 在 $mid$mid 左边, 于是 $r=mid-1$r=mid−1,
  否则 $l=mid+1$l=mid+1.

• 找到 分界点 后, 左区间不用管, 只需修改右区间
  列出几个转移 $\downarrow$↓
  $F\left[K\right]=F[K-1]+K\ast A\left[i\right]F[K+1]=F\left[K\right]+(K+1)\ast A\left[i\right]F[K+2]=F[K+1]+(K+2)\ast A\left[i\right]$F[K]=F[K−1]+K∗A[i]F[K+1]=F[K]+(K+1)∗A[i]F[K+2]=F[K+1]+(K+2)∗A[i]
  发现从 分界点 向右对 滚动数组 加个等差数列即可, 可以使用 线段树 或者 平衡树 实现, 这里用平衡树, 因为标程好拍

$实现部分$实现部分

$二分那里有点坑...$二分那里有点坑...

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e5 + 10;
const ll inf = 1e18;

int N;
int rot = 1;
int cnt = 1;
int fa[maxn];
int size[maxn];
int ch[maxn][2];

ll tag_d[maxn];
ll tag_a[maxn];
ll V[maxn];

bool chk(int x){ return ch[fa[x]][1] == x; }

void Push_up(int x){ size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; }

void Modify(int x, ll a1, ll d){
        tag_d[x] += d, tag_a[x] += a1;
        V[x] += a1 + d*(size[ch[x][0]] + 1);
}

void Push_down(int x){
        if(tag_d[x] || tag_a[x]){
                if(ch[x][0]) Modify(ch[x][0], tag_a[x], tag_d[x]);
                if(ch[x][1]) Modify(ch[x][1], tag_a[x]+tag_d[x]*(size[ch[x][0]] + 1), tag_d[x]);
                tag_d[x] = tag_a[x] = 0;
        }
}

void rotate(int x){ //
        int y = fa[x], z = fa[y], d = chk(x), s = ch[x][d^1];
        ch[y][d] = s, fa[s] = y;
        ch[z][chk(y)] = x, fa[x] = z;
        ch[x][d^1] = y, fa[y] = x;
        Push_up(x), Push_up(y);
}

void Splay(int x, int aim = 0){ //
        std::stack <int> stk;
        stk.push(x);
        int tmp = x;
        while(fa[tmp]) stk.push(fa[tmp]), tmp = fa[tmp];
        while(!stk.empty()) Push_down(stk.top()), stk.pop();
        while(fa[x] != aim){
                int y = fa[x], z = fa[y];
                if(z != aim){
                        if(chk(x) == chk(y)) rotate(y);
                        else rotate(x);
                }
                rotate(x);
        }
        rot = x;
}

ll Kth(int x){
        int t = rot;
        while(1){
                if(ch[t][0] && size[ch[t][0]] >= x) t = ch[t][0];
                else if(size[ch[t][0]] + 1 < x) x -= size[ch[t][0]] + 1, t = ch[t][1]; 
                else{ Splay(t); return V[t]; }
        }
}

ll Q_max(int x){
        if(!x) return -inf;
        Push_down(x);
        return std::max(V[x], std::max(Q_max(ch[x][0]), Q_max(ch[x][1])));
}

int Query(int i, int x){ 
        int s = i - 1; 
        int l = 0, r = i - 2;
        while(l <= r){ 
                ll mid = l+r >> 1; 
                if(Kth(mid+1) + (mid+1ll)*x > Kth(mid+2)) r = mid - 1, s = mid; 
                else l = mid + 1; 
        }
        return s;
}

void Add_node(){
        V[++ cnt] = V[rot];
        fa[cnt] = rot, fa[ch[rot][1]] = cnt;
        ch[cnt][1] = ch[rot][1], ch[rot][1] = cnt;
}

int main(){ 
// freopen("a.in", "r", stdin);
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++){
                int x;
                scanf("%d", &x);
                int K = Query(i, x) + 1;
                Kth(K), Add_node();
                Modify(cnt, 1ll*(K-1)*x, x);
        }
        printf("%lld\n", Q_max(rot));
        return 0;
}