社区讨论

贪心+DP能AC的原因

P1020[NOIP 1999 提高组] 导弹拦截参与者 6已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi6gfjeh
此快照首次捕获于
2025/11/20 04:28
4 个月前
此快照最后确认于
2025/11/20 04:28
4 个月前
查看原帖
这题数据有些过于弱了(或许是官方数据???当年不考Dilworth定理这么玄学的东西???)
CPP
100 10 100 10 100 10
^Z
这组数据如果使用贪心+DP不能过。
显然正解是:
CPP
4
2
DP+贪心会得出错误答案。有:
CPP
4
3
或者
CPP
2
3
或者什么别的乱七八糟的结果。
正解大概是两个DP(用Dilworth定理)???
完。

回复

8 条回复,欢迎继续交流。

正在加载回复...