2020-2021:teams:i_dont_know_png:week_summary_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/10 00:48] potassium |
2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/16 21:04] (当前版本) potassium |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020.05.04-2020.05.10 周报 ====== | + | ====== 2020.05.03-2020.05.09 周报 ====== |
| 团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。 | 团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。 | ||
| 行 84: | 行 84: | ||
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| - | 无 | + | [[2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1#E|[QkOI#R1] E Quark and Game]] 想不到 |
| ===== 个人训练 - Potassium ===== | ===== 个人训练 - Potassium ===== | ||
| 行 172: | 行 172: | ||
| **题意**：$n\leq 50$个任务，每个任务$a,b$两个属性$(1\leq a_i\leq 10^8,1\leq b_i\leq 100)$。有一些机器，每台机器可以执行最多两次任务，执行两次的时候要求第二个任务比第一个任务的$a$小。设第一次执行任务的集合为$S$，最小化$\frac{\sum_{i\in S}a_i}{\sum_{i\in S} b_i}$。 | **题意**：$n\leq 50$个任务，每个任务$a,b$两个属性$(1\leq a_i\leq 10^8,1\leq b_i\leq 100)$。有一些机器，每台机器可以执行最多两次任务，执行两次的时候要求第二个任务比第一个任务的$a$小。设第一次执行任务的集合为$S$，最小化$\frac{\sum_{i\in S}a_i}{\sum_{i\in S} b_i}$。 | ||
| - | **题解**：根据01分数规划套路，二分答案$m$，即求${\sum_{i\in S}a_i-mb_i}\leq 0$能否满足。按$a$从大到小、$a-m*b$从大到小排序，合并一下$a$相同的项，记录第$i$项有$cnt_i$个，按顺序枚举，分别加入$S$或补集$C_US$，有任意时刻$S$中元素多于$C_US$。于是设$f[i][j]$表示到$i$，有$j$个分配到$1$且可用（可分配一个$2$）的任务的最小值，则对于一个$i$，枚举分配给第二个任务的个数$k\in[0,cnt_i]$，有 | + | **题解**：根据01分数规划套路，二分答案$m$，即求${\sum_{i\in S}a_i-mb_i}\leq 0$能否满足。按$a$从大到小、$a-mb$从大到小排序，合并一下$a$相同的项（可以在$dp$的时候进行这一步，要记录第$i$项开始与第$i$项的$a$相同的元素有$cnt_i$个），按顺序枚举，分别加入$S$或补集$C_US$，有任意时刻$S$中元素多于$C_US$。于是设$f[i][j]$表示到$i$，有$j$个分配到$1$且可用（可分配一个$2$）的任务的最小值，则对于一个$i$，枚举分配给第二个任务的个数$k\in[0,cnt_i]$，有 |
| - | $$f[i][j+(cnt_i-k)-k]=min(f[i][j+(cnt_i-k)-k],f[i-1][j]+(cnt_i-k)\times (a_i-m\times b_i))$$ | + | $$f[i][j+(cnt_i-k)-k]=\min(f[i][j+(cnt_i-k)-k],f[i-1][j]+\sum_{l=i+k}^{i+cnt_i-1} (a_l-m\times b_l))$$ |
| 这题需要记录的地方在于，将相同的项合并，从而简化$dp$过程。 | 这题需要记录的地方在于，将相同的项合并，从而简化$dp$过程。 | ||
2020-2021/teams/i_dont_know_png/week_summary_1.1589042931.txt.gz · 最后更改: 2020/05/10 00:48 由 potassium
