【比赛经历】
- 先看完题，准备按顺序做。
- T1先写了一个\(O(NK^{2})\)的DP，交一发，得分8/10。
- 仔细一想，\(O(NK)\)的做法好像可行，但稍微有点难写，决定卡常+骗分。
- 把Max换成If语句，给循环变量加上人register，得分9/10。
- 4次提交后，发现T的那个测试点满足\(K≥90\)、\(N≥80000\)，针对性地骗分后，得到满分。
- 此时时间刚过1h。
- T2想了一段时间，得到一个\(O(N^{2})\)的算法，写完提交，得分2/11。
- 一会儿过后，发现一个较强的剪枝，加上后得到满分。（实际上存在能将这个算法卡到\(O(N^{2})\)的数据）
- 此时时间过了1.5h+。
- 仔细想了T3后发现是简单题，写完提交，顺利满分。
- 时间一共过了2h+。
- 总之这场比赛并不是每道题都会做，但通过一些奇技淫巧得到了满分，笔者还是很兴奋的
【T1】Lifeguards
【题目链接】
【题解链接】
【思路要点】
- 首先，如果区间A包含区间B，那么区间B是没有任何作用的，因此，被任何另一个区间包含的区间均可以被直接删除，并将\(K\)减1。
- 如此操作后，区间的左右端点均是单调的，因此可以简单地设计DP。设\(F_{i,j}\)表示考虑前\(i\)个区间，保留第\(i\)个区间，且已经放弃了\(j\)个区间时，可以覆盖的最长的长度。
- 显然有\(O(K)\)的转移，时间复杂度\(O(NK^{2})\)。
- 笔者在考场上的做法针对较大的数据进行了初步贪心，每次选取放弃的损失最小的区间放弃，将\(K\)降至较低的一个值，然后再进行DP，在考场上可以得到满分。下面的代码也是这种做法。
- 正确的做法应当是考虑将转移位置分为两种，一种是由与当前区间不相交的区间
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
