863. 国庆旅行

863. 国庆旅行

863. 国庆旅行

小明国庆节来北京玩，北京有N个景点，第 i 个景点的评分用a[i]表示，两个景点i, j之间的距离为j - i(j > i)。

小明一天只能游玩两个景点，我们认为总评分是两个景点的评分之和减去两个景点之间的距离，即为a[i]+a[j]+i-j。

那么小明选择哪两个景点才会总评分最大呢？

输入格式

第一行包含整数N。

第二行分别输入N个景点的评分。

输出格式

输出最大评分

数据范围

2≤N≤1052≤N≤105, 1≤a[i]≤10001≤a[i]≤1000

输入样例：

511 6 5 18 12

输出样例：

29

思路：

发现选两个点，双重循环。

然后枚举 j，从前 j个点中选第二个点的时候，可以求个前缀最大，就可以省掉一重循环。

代码：

#include #include #include #include #include #include using namespace std;#define ll long longconst ll mod = 1e9 + 7;const int INF = 0x3f3f3f3f;const int maxn = 1e5+10;int a[maxn];int main() { int n; cin >> n; for (int i = 1;i <= n;++i) { scanf("%d", &a[i]); } int ret = 0; int max_pre = 0; for (int i = 1;i <= n;++i) { ret = max(ret, max_pre + a[i] - i); max_pre = max(max_pre, a[i] + i); } cout << ret << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。