P10811 【MX-S2-T2】 排题目背景原题链接https://oier.team/problems/S2B。题目描述有n nn个整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1​,a2​,…,an​。$f_00,f_i \left{\begin{aligned} f_{i-1} \ f_{i-1}\times a_i0, \ f_{i-1}a_i \ f_{i-1}\times a_i\le 0.\\end{aligned}\right.$重排a aa使得得到的f n f_nfn​最大。输入格式第一行一个整数n nn。第二行n nn个整数a 1 , … , a n a_1,\dots,a_na1​,…,an​。输出格式一行一个整数表示答案。输入输出样例 #1输入 #15 7 5 -4 -6 3输出 #16输入输出样例 #2输入 #210 573 -1339 899 939 -26 1430 1324 -1150 1640 -45输出 #21625说明/提示【样例解释 #1】考虑重排为− 6 , − 4 , 5 , 7 , 3 -6,-4,5,7,3−6,−4,5,7,3最终的f n f_nfn​为6 66可以证明不存在更优的方案。【数据范围】本题采用捆绑测试。Subtask 06 ptsn ≤ 10 n\le10n≤10。Subtask 114 ptsn ≤ 20 n\le 20n≤20∣ a i ∣ ≤ 10 |a_i|\le10∣ai​∣≤10。Subtask 28 ptsa aa中全为正数或全为负数。Subtask 319 ptsa aa中有且只有一个正数注意a aa中可以有0 00。Subtask 429 ptsn ≤ 200 n \le 200n≤200∣ a i ∣ ≤ 200 |a_i|\le 200∣ai​∣≤200。Subtask 524 pts无特殊限制。对于所有测试数据1 ≤ n ≤ 2000 1 \le n \le 20001≤n≤2000∣ a i ∣ ≤ 2000 |a_i|\le 2000∣ai​∣≤2000。C实现#includebits/stdc.husingnamespacestd;constintiinf0x3f3f3f3f;constintst2000001;intn;inta[2011];vectorintse;bitset4000011f;signedmain(){cinn;for(inti1;in;i)cina[i];for(inti1;in;i)if(a[i])se.push_back(a[i]);sort(se.begin(),se.end());boolflgtrue;for(inti1;in;i)if(a[i]*a[1]0)flgfalse;if(se.empty())cout0;elseif(flg)coutse[se.size()-1];else{for(inti0;ise.size()-1;i){if(se[i]0)f|fse[i];elsef|f-se[i];f[stse[i]]1;}intma-iinf;for(intist-2000;ist;i)if(f[i])mai;coutma-stse[se.size()-1];}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容