牛客练习赛29-A 可持久化动态图上树状数组维护01背包

可持久化动态图上树状数组维护01背包
请允许我吐槽一下这个劝退人的题目,实际题与题目无关。
题目:

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

求把整个序列删完的最小代价。

输入描述:

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

输出描述:

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

示例1

输入

复制

2
3 2

输出

复制

5
#include<bits/stdc++.h>
#define MAX 1000010
using namespace std;
long long arr[MAX];
int main(){
    long long int n;
    long long int sum=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=n;i>0;i--){
        if(arr[i]>=0)
            sum+=arr[i];
        else{
            sum+=i*arr[i];
        }
    }
    cout<<sum<<endl;
    return 0;
}

题意:贪心,整数最终能以权为1的情况删除,而负数不行,因为负数乘权能对答案贡献正值所以必须保持原权不变小,变大无法操作所以必须按照原权删除。

贪心策略:正数相加,负数原权删除

发表评论

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

15 + 9 =