luogu#P7319. 「PMOI-4」生成树

「PMOI-4」生成树

题目背景

题目正解不会很难,反正很难的也必不会做,所以宁愿相信题目都是善良的。

——command_block 《考前小贴士》

djy 出了一道生成树的题,然后发现做法假了,就把这个题改了一下,作为这场比赛的 B。

题目描述

给定 nn 个数,第 ii 个数的原始权值是 wiw_i,你要按照某种顺序将这些数依次选择。

若当前是第 ii 次选数,选择的原始权值kk,则其他所有未被选过的数的权值均加上 (1)i+k+1×k(-1)^{i+k+1} \times k

你需要求出一种选数方案,使得选出的 nn 个数最终权值最大

输入格式

第一行一个正整数 nn

第二行 nn 个整数 wiw_i,表示第 ii 个数的权值。

输出格式

一行一个整数,表示最大权值和。

7
1 -1 -2 2 -3 3 4
66

提示

【样例解释】

依次选择编号{7,6,5,3,4,1,2}\{7,6,5,3,4,1,2\} 的数即可。

【数据范围】

本题采用捆绑测试

  • Subtask 1(20pts):n7n \le 7
  • Subtask 2(30pts):n103n \le 10^3
  • Subtask 3(30pts):保证所有的 wi0w_i \ge 0 或所有的 wi0w_i \le 0
  • Subtask 4(20pts):无特殊限制。

对于 100%100\% 的数据满足,1n105,109w1091 \le n \le 10^5,-10^9 \le w \le 10^9