Maximize The Beautiful Value (前缀和&贪心）

题目传送门

题意：给定长度为n不递减序列，求操作一次使其F[n]最大。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],pre[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,k,ans=0,mx=-1e15;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i],ans+=a[i]*i;
        for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
        for(int i=k+1;i<=n;i++)
        {
                if(pre[i-1]-pre[i-k-1]-a[i]*k>mx){
                    mx=max(mx,pre[i-1]-pre[i-k-1]-a[i]*k);
                }
        }
        cout<<ans+mx<<endl;
    }
    return 0;
}