※ 引述《babufong (哔哔)》之铭言： : 371. Licence plates : http://projecteuler.net/problem=371 : 俄勒冈州的车牌号码是由三个英文字母後面接着三位数字(0到9)所组成的。 : Seth 开车去上班时，他会玩一个小游戏： : 每当他在路途上，看到两个车牌号码的数字部分相加为 1000 时，就算胜了这场游戏。 : (如 MIC-012 和 HAN-988，或是 RYU-500 和 SET-500，这都算胜利，只要是在同一趟 : 车程中看到。） : 计算出 Seth 赢得游戏所需要看到的车牌数的期望值，并将答案给到小数点後八位数。 一开始往马可夫链的方面去想，结果被困了好久 最後灵光一闪，发现了其实只是个简单的DP题 车牌英文字母不重要, 因为对每一个数字来说，每一种3位英文字母出现的机率相等 所以问题简化成只有数字相加 要加成1000, 一共有1+999, 2+998, 3+997, ...., 499+501, 500+500；500种配对 500比较特殊，要另外讨论，所以是499个数字配对和跟有没有500 DP的状态是500*2 表示499对数字中,有几对已经在「听牌状态」了，跟有没有500数字在其中，所以是500*2 已出现的数字是{2,3,499}跟{7, 23, 888}没有不同，在DP上，都是属同一个状态 皆是表示有3对数字在「听牌状态」 「听牌状态」是我发明的辞，表示一个数对已有其中之一被看到， 在等待另一个数字凑成1000 接下来是求取每一次看见车牌，还无法凑成1000的机率 假设在第n次看见车牌後，还无法凑成1000的机率为p_n(注: 用 _ 表示下标) 很显然的 在前一次尚未凑成1000，而在这次凑成1000的机率为(1-p_n)-(1-p_(n-1))=p_(n-1)-p_n 期望值为 sigma(2<=n=∞) (p_(n-1)-p_n)*n 很直觉的，p_1=1 p_2以後就用DP算出 差不多算到第300次看见车牌，p_n就衰减到近乎於零 所以算到300次即可 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.62.203.103 ※ 编辑: utomaya 来自: 61.62.203.103 (02/13 09:45)