主题：TJU1004 防御导弹，虽然提交成功但还是不明白。
eastcowboy
[专家分：25370] 发布于 2005-05-26 20:55:00
连接如下：
http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1004
根据题目的要求输出M和N。
M的值比较好办，用穷举就可以搞定。关键是求N，我用了贪心法，提交成功了，但是怎么想也不明白为什么可以这样做？
回复列表 （共14个回复）
沙发
faintzw [专家分：2660] 发布于 2005-05-26 21:59:00
m你穷举的？？汗…………
板凳
davidw017 [专家分：4170] 发布于 2005-05-27 17:52:00
……那么把你穷举的部分做成一个函数，然后用过的标记……至于你这个……可能数据不爽？！
3 楼
sb191919 [专家分：40] 发布于 2005-05-28 17:52:00
穷举什么??!!!
糟蹋动态规划题
[em9][em9][em9][em9][em9]
4 楼
davidw017 [专家分：4170] 发布于 2005-05-28 19:28:00
的确是 dp 题，但是 dfs 也能过……
5 楼
eastcowboy [专家分：25370] 发布于 2005-05-28 21:25:00
数学不好，现在会的解题思路不多啊。穷举倒是比较明白，是用了深度优先搜索，至于动态规划，我现在还是个门外汉。
我只是想知道，求N用贪心法到底对不对？自己总感觉可能有问题，不能找到精确解。
6 楼
faintzw [专家分：2660] 发布于 2005-05-29 09:15:00
n就是用贪心求的。
能否把你穷举的程序贴出来看看？depth=100的深搜……
7 楼
kingwei [专家分：3960] 发布于 2005-05-31 19:51:00
穷举?! 寒~~~~~~~~~
8 楼
eastcowboy [专家分：25370] 发布于 2005-06-01 23:42:00
题目说了不多于20个数嘛，100个数的话，穷举多半是无效算法了。
9 楼
faintzw [专家分：2660] 发布于 2005-06-02 23:46:00
啊……记成n<=100了
10 楼
不是归人 [专家分：1400] 发布于 2005-06-07 13:32:00
一个是求最长正序子列，另一个是求最长逆序子列，都是一样一样一样滴。
我来回复
您所在位置：