#NC19838. 可持久化动态图上树状数组维护01背包
可持久化动态图上树状数组维护01背包
题目描述
你有一个长度为 n 序列 {a}(序列下标从1开始) ,每次可以从任意位置 i 花费 ai*i 的代价来把 ai 删除。
注意,删除后 ai 后面的数会依次向前补上(下标 -1 ) 。 求把整个序列删完的最小代价。
输入格式
第一行一个整数 n ,第二行 n 个整数代表该序列。
输出格式
一行一个整数表示删完序列的最小代价。
提示
保证答案在 到 范围内。
样例 1
2
3 2
5
你有一个长度为 n 序列 {a}(序列下标从1开始) ,每次可以从任意位置 i 花费 ai*i 的代价来把 ai 删除。
注意,删除后 ai 后面的数会依次向前补上(下标 -1 ) 。 求把整个序列删完的最小代价。
第一行一个整数 n ,第二行 n 个整数代表该序列。
一行一个整数表示删完序列的最小代价。
保证答案在 −263 到 263−1 范围内。
2
3 2
5