5.19 每日一题题解

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

• 题目链接：https://ac.nowcoder.com/acm/contest/211/A

涉及知识点：

• 贪心

solution：

• (假设这n个数都是正数，最小代价就是他们的和)
• (比如1，2，3，4，我们直接从前往后删的代价 = 1 + 2 + 3 + 4)
• (出现负数怎么办？)
• (要让答案尽可能地小，就要保证负数的下标i尽可能的大)
• (但是下标不能后移，所以从最后一个负数往前删)
• (这样能保证每个负数的贡献等于它本身乘以下标)
• (答案就等于正数的和加上负数乘以相应的下标的和)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
    int n;
    ll x, ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x < 0)
            ans += 1ll*i*x;
        else 
            ans += x;
    }
    cout<<ans<<endl;
    return 0;
}