luogu#P7319. 「PMOI-4」生成树
「PMOI-4」生成树
题目背景
题目正解不会很难,反正很难的也必不会做,所以宁愿相信题目都是善良的。
——command_block 《考前小贴士》
djy 出了一道生成树的题,然后发现做法假了,就把这个题改了一下,作为这场比赛的 B。
题目描述
给定 个数,第 个数的原始权值是 ,你要按照某种顺序将这些数依次选择。
若当前是第 次选数,选择的原始权值为 ,则其他所有未被选过的数的权值均加上 。
你需要求出一种选数方案,使得选出的 个数最终的权值和最大。
输入格式
第一行一个正整数 。
第二行 个整数 ,表示第 个数的权值。
输出格式
一行一个整数,表示最大权值和。
7
1 -1 -2 2 -3 3 4
66
提示
【样例解释】
依次选择编号为 的数即可。
【数据范围】
本题采用捆绑测试。
- Subtask 1(20pts):。
- Subtask 2(30pts):。
- Subtask 3(30pts):保证所有的 或所有的 。
- Subtask 4(20pts):无特殊限制。
对于 的数据满足,。