可持久化动态图上树状数组维护01背包

题目

有一个长度为 $n$ 序列 $\{a\}$ （序列下标从 1 开始），每次可以从任意位置 $i$ 花费 $a_i \times i$ 的代价来把 $a_i$ 删除。
注意，删除后 $a_i$ 后面的数会依次向前补上（下标 -1 ) 。
求把整个序列删完的最小代价。

解题思路

当 $a_i$ 是正数时，在下标 1 的位置删除代价最小，即 $a_i \times 1 = a_i$ 。
当 $a_i$ 是负数时，在其当前所在下标的位置删除代价最小，即 $a_i \times i$ ，因为下标不能更大了。

C++代码

#include<cstdio>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    long long ans = 0;
    int a;
    for(int i=0; i<n; ++i){
        scanf("%d", &a);
        if(a<0)
            ans += 1LL*a*(i+1);
        else
            ans += a;
    }
    printf("%lld", ans);
    return 0;
}