2020-2021:teams:too_low:cf655ef_hj
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:cf655ef_hj [2020/09/04 17:19] jim |
2020-2021:teams:too_low:cf655ef_hj [2020/09/04 17:51] (当前版本) jim [E. Omkar and Last Floor] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| * 题意：一个n*m矩阵，每一行被分割成了多个片段，每个片段中填一个1，使每列1个数的平方和最大。输出最大结果。m，n<100 | * 题意：一个n*m矩阵，每一行被分割成了多个片段，每个片段中填一个1，使每列1个数的平方和最大。输出最大结果。m，n<100 | ||
| + | |||
| * 分类：dp、贪心 | * 分类：dp、贪心 | ||
| 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | ||
| - | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。 | ||
| - | 考虑1尽可能集中到第i列，那么有dp[l][r] = dp[l, i-1] + dp[i+1, r] + 被i分割，且位于[l,r]区间内的的片段数 | + | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。考虑1尽可能集中到第i列，那么有dp[l][r] = dp[l, i-1] + dp[i+1, r] + 被i分割，且位于[l,r]区间内的的片段数 |
| 对枚举i后取最大值即可得到dp[l][r] | 对枚举i后取最大值即可得到dp[l][r] | ||
| - | + | * comment: 这道题m，n较小，可以容纳维度更高的dp。主要是需要确定dp时分割片段的标准。 | |
| <code cpp> | <code cpp> | ||
| 行 79: | 行 78: | ||
| 因此大约每两次询问可以定位一个数字。 | 因此大约每两次询问可以定位一个数字。 | ||
| + | |||
| + | * comment：这道题的询问次数限制很少，分治时要特别注意log的消除 | ||
| <code cpp> | <code cpp> | ||
2020-2021/teams/too_low/cf655ef_hj.1599211196.txt.gz · 最后更改: 2020/09/04 17:19 由 jim
