作者yoco315 (眠月)
站内Prob_Solve
标题Re: [问题] 人生成就问题
时间Thu Apr 22 01:38:01 2010
※ 引述《ECZEMA (加油!)》之铭言：
: 小学 国中 高中 大学
: ┌──┐ ┌──┐ ┌──┐ ┌──┐
: │ 甲 │ │ A │ │ 1 │ │ Ⅰ │
: │ 乙 │ │ B │ │ 2 │ │ Ⅱ │
: └──┘ └──┘ └──┘ └──┘
把问题简化一下的话，
变成只有两个人，问「怎麽选两条路径，其分数和最高」。
又因为两人不得为同学，故一个人选某一班，另一个人就得选另外一班，
如果第一个人在某一阶段选 0 班，另一个人就必选 1 班。
这问题即可简化成「一 binary string，其分数由查表得知，求分数最大者」，
至此显然可知，若分数表无特殊性质，则此问题必为 NP。
解法就是试过所有的 binary string 组合。
如果只有两班可以选，复杂度为 O(2^(stage-1))。
如果有 n 班可以选，复杂度为 O( n!^(stage-1) )。
如果 stage 如原题限定只有四阶、五班，
120 ^ 3 = 1,728,000，其实很小，可解 XD
再多一阶的话就是 207,360,000，用力一点跑还是可以啦～
再多一阶就 24,883,200,000 了，应该就不会想算了
至於 1000 阶的话......
我只能说这个人好可怜，书要念这麽久.......... XD
--
To iterate is human, to recurse, divine.
递回只应天上有, 凡人该当用回圈. L. Peter Deutsch
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.160.115.200
1F：推 LPH66:推一个 04/22 07:47
2F：推 linjack:厉害 <(_ _)> 04/22 10:06
3F：推 keeperkai:所以其实最後就只能用暴力法? 04/22 20:53
4F：→ ECZEMA:可是我的是 1000 班 四阶… (1000!)^3 也满惨的~ 04/24 13:42