2020.7.12 牛客多校第一场

2020.7.13 牛客多校第二场

• 动态规划 部分本周填坑 by iuiou

• atcoder beginner contest 173
• atcoder AIsing Programming Contest 2020

• 题意：有一些物品，现已知第i个物品放在前$k_i$位置时产生的贡献为$l_i$,否则产生的贡献为$r_i$，问如何排布才能使总贡献取到最大？

• 知识点：stl，贪心，堆

• 题解：这题设计多条件限制最值。思路如下：首先可以将所有数分成两组，一组是满足l>r的，另一组是满足r>l的，显然第一组的物品尽量往前靠，后一组的物品尽量往后靠，其实两组通过划归可以归为一个问题，不妨考虑第一组，每个数都有基础贡献$r_i$,之后考虑$k_i$，k越小越要排前面，所以将第一组按照k的值排序，同时开一个小根堆维护l-r的值，遍历第一组的物品，一旦k的值小于堆的总量就插入，否则若k等于堆的总量，则比较l-r的值。这样最后将堆中的数加进答案即可。对于放后面的情况可以转化为前面的情况。总复杂度$O(n\log n)$

• atcoder AIsing Programming Contest 2020(QuantumBolt)

这位同志生病中，咕咕咕。

无