• 前言
• 题目描述
• 思路
  • 大体思路
  • 为什么这样是正确的
• 总结
• 代码

前言

主要使用了贪心的思想，使用C++语言。感觉T3比T2简单

题目描述

给定一个长度为 $n$ 的数组 $a[1...n]$，你需要找到一个相同长度的数组 $b[1...n]$，满足：

• $b[1] = 0$
• 对于 $i=2...n$，满足$0\le b[i]\le b[i-1]+1$
• $ans = \sum a[i]\times b[i] = a[1]\times b[1] + a[2]\times b[2] + ... + a[n]\times b[n]$ 的值最大

请你输出这个最大的 $ans$ 值

对于所有测试点，满足：$1\le n\le 10^6, -1000 \le a[i] \le 1000$

思路

大体思路

首先可以知道，任意一位都可以马上回到0。之后稍微思考可以得到，所谓的 $0\le b[i]\le b[i-1]+1$ 没有意义，因为如果是正数的话必然 $b[i]$ 越大越好，负数的话为 $0$ 最好。然后可以从后往前扫了，这样的话最后面的数字就是最大的，顺序不会乱。计算一个变量 $sum$，如果 $sum$ 还依然 $>0$，那么就可以暂时把 $b[i]$ 设为 $1$，代表之后要用。等做完了之后，如果 $b[i]=1$，那么就可以让 $b[i]=b[i-1]+1$，然后 $ans+=a[i]*b[i]$ 即可。

为什么这样是正确的

$1,2,3$ 这么乘的话就算前面有亏损到了后面赚的时候也一定能赚回来，如果真的这一阶段亏到负数了，就及时的停止第一个亏的部分。然后前面的接着开始，这样一定是最优的，可以自己画几个图理解一下。

总结

本题的难点在于想到倒着推这一点。其次将这个看着复杂的问题化简也是一个难点。注意到只有 $0$ 和 $b[i]$ 最大。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll n,a[MAXN],b[MAXN];
int main(){
    cin>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>a[i];
    }
    ll sum=0;
    for (ll i = n; i >=2 ; --i) {
        sum+=a[i];
        if(sum<0){
            sum=0;//开始亏损了要马上停止
        }else{
            b[i]=1;//这里可以走
        }
    }
    ll ans=0;
    for (int i = 2; i <=n ; ++i) {
        if(b[i]){
            b[i]=b[i-1]+1;//模拟
            ans+=a[i]*b[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}