链接:https://www.nowcoder.com/acm/contest/211/A
来源:牛客

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

2
3 2

输出

5

备注:

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

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

思路其实很简单,值得注意的一点就是负数,正数的权肯定是越小越好,负数的权肯定是越高越好,正数肯定是会被消去,所以都让他们权重为1就行了,负数的话,从后往前删,权重越高越好。一个是我的AC代码,比赛的时候没转过来,开了个数组,后面那个代码是空间时间复杂度都很小的一个。

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

2 Replies to “牛客练习赛29-A”

  1. Google Chrome 63.0.3239.132 Google Chrome 63.0.3239.132 Windows 10 x64 Edition Windows 10 x64 Edition
    Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36

    这个题的名字真变态

    1. Firefox 62.0 Firefox 62.0 Windows 10 x64 Edition Windows 10 x64 Edition
      Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:62.0) Gecko/20100101 Firefox/62.0

      确实……不过也很水

发表评论

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