演艺圈和老同志真是提高国民素质道路上的两座大山 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

演艺圈和老同志真是提高国民素质道路上的两座大山

演艺圈和老同志真是提高国民素质道路上的两座大山# Joke - 肚皮舞运动

f*d2013-07-22 07:07

1 楼

继续问题，跪求大牛帮忙扫:)
Given a dictionary and a string, write a program to output the valid words
while minimizing the numbers of skipped characters. The substring that
consists of a valid word in the dictionary may swap the characters. For
example, Given a dictionary d = window, cat and a string “iwndowdcta”, the
output is “window cat”. In this case, there is only one number of skipped
character which is ’d’.
多维背包？但是这个维度(#of alphas in language)还是太高了吧。有其它好的解法吗？

B*92013-07-22 07:07

2 楼

H*g2013-07-22 07:07

3 楼

【以下文字转载自 Military 讨论区】
发信人: cityfish (给我点儿阳光，让我灿烂), 信区: Military
标题: Re: 气功大师悍马接待赵薇李连杰 15个手榴弹炸不坏zt
发信站: BBS 未名空间站 (Mon Jul 22 08:35:38 2013, 美东)
末法时代，妖孽频出啊
这个王林不仅和演艺圈走的进
看微薄上爆料，挖出来他和领导人的合影也不少
贾庆林，李瑞环，吴官正，钱其琛，全都有。当年李洪志都没这个待遇吧？
演艺圈和老同志真是提高国民素质道路上的两座大山。
势。

a*m2013-07-22 07:07

4 楼

每个词都可以用一个长度＃的数组表示，然后把字典建成一个＃维数组。最后背包部分
还算可以接受吧，少于＃维恐怕难。

l*o2013-07-22 07:07

5 楼

大变活蛇，nnd,还能更离谱点么。。

f*d2013-07-22 07:07

6 楼

借这题再问大牛一个相关的问题，如果维度不确定的dp，比如说依赖于输入，那在实现
上好做吗？具体一点的等价问题，如果知道是26维dp，可以避免写26层的循环吗？也
许借助递归可以很好的实现，记忆化dp？请大牛confirm一下！

【在 a********m 的大作中提到】

: 每个词都可以用一个长度＃的数组表示，然后把字典建成一个＃维数组。最后背包部分
: 还算可以接受吧，少于＃维恐怕难。

z*32013-07-22 07:07

7 楼

至少没有大变活龙

【在 l*****o 的大作中提到】

: 大变活蛇，nnd,还能更离谱点么。。

b*m2013-07-22 07:07

8 楼

如果我没理解错的话,
可以简化为shortest path 问题。
不过这种题我得想20分钟才能想出思路来。

M*e2013-07-22 07:07

9 楼

明明是个行艺大师，乔版的有点幽默感哦。

【在 z*****3 的大作中提到】

: 至少没有大变活龙

p*u2013-07-22 07:07

10 楼

感觉这是个网络流问题。
假设词典有n个单词，每个单词最后在string中出现的次数为f[i]，根据26个字母，可
以列26个不等式，比如例子中w的不等式为：
2 * f[0] + 0 * f[1] <= 2
目标方程：z = len(string) - f[0] * len(dict[0]) - f[1] * len(dict[1]) - ...
求z的最小值，用网络流的方法就可以了。

the
skipped
吗？

【在 f*********d 的大作中提到】

: 继续问题，跪求大牛帮忙扫:)
: Given a dictionary and a string, write a program to output the valid words
: while minimizing the numbers of skipped characters. The substring that
: consists of a valid word in the dictionary may swap the characters. For
: example, Given a dictionary d = window, cat and a string “iwndowdcta”, the
: output is “window cat”. In this case, there is only one number of skipped
: character which is ’d’.
: 多维背包？但是这个维度(#of alphas in language)还是太高了吧。有其它好的解法吗？

wy2013-07-22 07:07

11 楼

jp很多啊。美国情报部门请他出国定居，承诺给他70张绿卡，而他舍不得家乡不肯去。

【在 H********g 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: cityfish (给我点儿阳光，让我灿烂), 信区: Military
: 标题: Re: 气功大师悍马接待赵薇李连杰 15个手榴弹炸不坏zt
: 发信站: BBS 未名空间站 (Mon Jul 22 08:35:38 2013, 美东)
: 末法时代，妖孽频出啊
: 这个王林不仅和演艺圈走的进
: 看微薄上爆料，挖出来他和领导人的合影也不少
: 贾庆林，李瑞环，吴官正，钱其琛，全都有。当年李洪志都没这个待遇吧？
: 演艺圈和老同志真是提高国民素质道路上的两座大山。
: 势。

a*m2013-07-22 07:07

12 楼

赞。

【在 p*u 的大作中提到】

: 感觉这是个网络流问题。
: 假设词典有n个单词，每个单词最后在string中出现的次数为f[i]，根据26个字母，可
: 以列26个不等式，比如例子中w的不等式为：
: 2 * f[0] + 0 * f[1] <= 2
: 目标方程：z = len(string) - f[0] * len(dict[0]) - f[1] * len(dict[1]) - ...
: 求z的最小值，用网络流的方法就可以了。
:
: the
: skipped
: 吗？

a*m2013-07-22 07:07

13 楼

多维背包记得不需要那么多循环。实现上应该区别不大，递归应该是要用到。不过这题
写起来恐怕挺麻烦的。

【在 f*********d 的大作中提到】

: 借这题再问大牛一个相关的问题，如果维度不确定的dp，比如说依赖于输入，那在实现
: 上好做吗？具体一点的等价问题，如果知道是26维dp，可以避免写26层的循环吗？也
: 许借助递归可以很好的实现，记忆化dp？请大牛confirm一下！

t*a2013-07-22 07:07

14 楼

可以用DP来做。计算复杂度大约为n^3*len(dict)
假设输入字符串s长度为n，f为求解的函数，那么
f(s, dict) = match_dict(s, dict) 当s可以直接匹配上dict里的某字符串（通过排序
后比较）, match_dict返回dict中匹配上的字符串
f(s, dict) = (max the words length) [f(subs(s, 0, i), dict), f(subs(s, i, n)
, dict)], i=1..n-1 当s不能直接找到dict里的匹配
f(s, dict) = nil 当s为空
clojure程序如下
(defn gen-sorted-dict [dict]
(reduce merge (for [w dict]
{(sort w) w})))
(defn match-dict [s sorted-dict]
(sorted-dict (sort s)))
(def prob10-sub
(memoize
(fn [s sorted-dict]
(when (not (empty? s))
(if-let [mw (match-dict s sorted-dict)]
[mw]
(let [mws (for [i (range 1 (count s))
:let [s1 (subs s 0 i)
m1 (prob10-sub s1 sorted-dict)
s2 (subs s i)
m2 (prob10-sub s2 sorted-dict)
m12 (concat m1 m2)]
:when (not (empty? m12))]
m12)]
(first (sort-by #(reduce + (map count %)) > mws))))))))
(defn prob10 [s dict]
(prob10-sub s (gen-sorted-dict dict)))
(prob10 "iwndowdcta" ["window" "cat"]) ;("window" "cat")
(prob10 "iwndowdctatc" ["windowdc" "cat"]) ;("windowdc" "cat")

c*n2013-07-22 07:07

15 楼

用二维 DP 做:
Define f_k(i) the number of skipped characters with string s[i,i+k).
Starting from k = 1 initializing f_1(i) = 0 if s[i] is in dict, f_1(i) = 1
otherwise; then calculate f_{k}(i) recursively by
f_{k+1}(i) = min_{h=1}^{k} {f_h(i) + f_{k+1-h}(i+h)} if s[i,i+k+1) is NOT in
dict; otherwise f_{k+1}(i) = 0;
up to k = len(s)
如何判断 s[i,i+k) is in Dict? One-pass preprocessing
Sol(1): the signatures of all words in Dict: the frequencies of letters in
that word, 然后按这个 signature 排序。
Sol(2): Hash table all words

c*e2013-07-22 07:07

16 楼

觉得一维dp就可以了
F(0) = 0;
string s, length N
i=1, 2, ..., N
F(i) = Min_j (F(j-1)+ isDict(s(j-1,i)) ? 0 : i-j+1 ) where j = i,...,1
s(j-1,i) includes chars [j-1, i)

in

【在 c*****n 的大作中提到】

: 用二维 DP 做:
: Define f_k(i) the number of skipped characters with string s[i,i+k).
: Starting from k = 1 initializing f_1(i) = 0 if s[i] is in dict, f_1(i) = 1
: otherwise; then calculate f_{k}(i) recursively by
: f_{k+1}(i) = min_{h=1}^{k} {f_h(i) + f_{k+1-h}(i+h)} if s[i,i+k+1) is NOT in
: dict; otherwise f_{k+1}(i) = 0;
: up to k = len(s)
: 如何判断 s[i,i+k) is in Dict? One-pass preprocessing
: Sol(1): the signatures of all words in Dict: the frequencies of letters in
: that word, 然后按这个 signature 排序。