Problem - D - Codeforces

有一条长为n的街道，其中第i个景点距离街道起点i英里。第i个景点的美丽值为bi。你想要在离街道起点l英里和r英里处开始和结束慢跑。当你跑步时，你会看到你经过的景点（包括起点和终点处的景点）。你对沿途慢跑时最美丽的三个景点感兴趣，但是随着你奔跑的英里数增加，你会越来越累。

因此，请选择l和r，使您途中至少经过3个景点，并且三个最美丽的景点的美丽数之和减去您必须奔跑的英里数最大化。更正式地，选择l和r，使得bi1+bi2+bi3−(r−l)的值最大，其中i1、i2和i3是范围[l,r]内三个最大元素的索引。

输入格式： 第一行包含一个整数t（1≤t≤105）——测试用例的数量。 每个测试用例的第一行包含一个整数n（3≤n≤105）。 每个测试用例的第二行包含n个整数bi（1≤bi≤108）——表示街道上第i个景点的美丽值。

保证所有n的总和不超过105。

输出格式： 对于每个测试用例，输出一个整数，表示某些奔跑区间[l,r]的最大值bi1+bi2+bi3−(r−l)。

Example

Input

Copy

4

5

5 1 4 2 3

4

1 1 1 1

6

9 8 7 6 5 4

7

100000000 1 100000000 1 100000000 1 100000000

Output

Copy

8
1
22
299999996

在第一个例子中，我们可以选择 l 和 r 为 1 和 5。因此，我们参观了所有景点，其中美丽值最大的三个景点是索引为 1、3、5 的景点，其美丽值分别为 5、4 和 3。因此，总价值为 5+4+3-(5-1)=8。

在第二个例子中，范围 [l, r] 可以是 [1,3] 或 [2,4]，总价值为 1+1+1-(3-1)=1。

题解:
如果写一道题没什么思路,试试转换一下题目中所给公式,变形一下

假设要选的三个值

左边的为al 中间为am 右边为ar

al + am + ar - (r - l)可以变形为

al + l + ar - r + am

我们可以分别得到前缀后缀最大值

然后枚举am即可求出答案

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;#define int long long
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 4e5 + 10;
int mod = 1e9 + 7;
int pre[N];
int las[N]; 
int a[N];
void solve()
{int n;cin >> n;las[n + 1] = -1e9;pre[0] = -1e9;for(int i = 1;i <= n;i++){cin >> a[i];}for(int i = 1;i <= n;i++){pre[i] = max(pre[i - 1],a[i] + i);}for(int i = n;i >= 1;i --){las[i] = max(las[i + 1],a[i] - i);}int ans = 0;for(int i = 2;i < n;i++){ans = max(ans,a[i] + las[i + 1] + pre[i - 1]);}cout << ans <<"\n";
}
signed main()
{ios::sync_with_stdio(0 );cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve(); }
}