题目描述

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

输入描述:

第一行一个整数 n ，第二行 n 个整数代表该序列。

输出描述:

一行一个整数表示删完序列的最小代价。

示例1

输入

2
3 2

输出

5

备注:

1<=n<=106，|ai|<=107

保证答案在 (-264,264) 范围内

题解

#include<cstdio>
using namespace std;
long long  a[1000005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	long long answer=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=0){
			answer+=a[i];
		}
		else{
			answer+=a[i]*i;
		}
	}
	printf("%lld",answer); 
	return 0;
}

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

原文：https://www.cnblogs.com/fate-/p/13303592.html