P10709 [NOISG 2024 Prelim] Party

题目描述James 有 n 个朋友他想选择其中的 0 个或者更多朋友来参加他的聚会。第 i 个朋友如果参加了他的聚会会产生 ai​ 点快乐值。注意有些朋友并不想参加聚会所以他们的 ai​ 会是负的。然而他家只有一排 n 个座位而且因为社交距离两个人不能坐在相邻的座位上。现在 James 想知道如果他按照最优方案邀请朋友这些朋友的快乐值的和最大为多少。输入格式第一行一个整数 n。第二行 n 个整数表示 a。输出格式一行一个整数表示答案。输入输出样例输入 #1复制运行5 3 2 -1 4 5输出 #1复制运行12输入 #2复制运行1 10输出 #2复制运行10输入 #3复制运行6 1 -3 2 10 -4 9输出 #3复制运行21说明/提示【样例 #1 解释】James 可以邀请第 1,4,5 位朋友。【样例 #2 解释】James 可以邀请唯一一位朋友。【样例 #3 解释】James 可以邀请第 3,4,6 位朋友。【数据范围】Subtask分值特殊性质00样例149n≤3238n≤1000313无对于 100% 的数据1≤n≤2×,−≤≤。记得开long long!!!!!!!!不然就会。。。。。。#includebits/stdc.h using namespace std; int a[200005]; int main(){ long long n; cinn; for(int i1;in;i){ cina[i]; } sort(a1,an1); int tn; if(n%2){ t; } t/2; int s0; for(int in;in-t;i--){ if(a[i]0){ break; } sa[i]; } couts; return 0; }相信你们一定会开的:#:*~*:#:正解#includebits/stdc.h using namespace std; int a[200010]; int main(){ long long n; cinn; for(int i1;in;i){ cina[i]; } sort(a1,an1); int tn; if(n%2){ t; } t/2; long long s0; for(int in;in-t;i--){ if(a[i]0){ break; } sa[i]; } couts; return 0; }恭喜你又A了一道题