o********r
发帖数: 79 | 1 from career cup.
You are given a String number containing the digits of a
phone number (the number of digits, n, can be any positive integer) . To
help you memorize
the number, you want to divide it into groups of contiguous digits. Each
group must contain
exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example,
000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030
, 229 or 166.
• U | k**********i
发帖数: 177 | 2 这个是用greedy 还是 dynamic programming 呢？
,
030
【在 o********r 的大作中提到】
: from career cup.
: You are given a String number containing the digits of a
: phone number (the number of digits, n, can be any positive integer) . To
: help you memorize
: the number, you want to divide it into groups of contiguous digits. Each
: group must contain
: exactly 2 or 3 digits. There are three kinds of groups:
: • Excellent: A group that contains only the same digits. For example,
: 000 or 77.
: • Good: A group of 3 digits, 2 of which are the same. For example, 030
| x******3
发帖数: 245 | 3 DP肯定是可以吧， greedy的话哪位大侠说下呗 | k**********i
发帖数: 177 | 4 DP的话应该也不是很快吧。。。我在careercup上看到有人用了greedy 写的
【在 x******3 的大作中提到】
: DP肯定是可以吧， greedy的话哪位大侠说下呗
| x******3
发帖数: 245 | 5 能说下intuition，greedy为啥能行不
我咋觉得greedy不行啊
比如771
用greedy的话，就先选77一组， 但是接下来没法坐了啊， 就剩一个数字了
【在 k**********i 的大作中提到】
: DP的话应该也不是很快吧。。。我在careercup上看到有人用了greedy 写的
| B*****t
发帖数: 335 | 6 where is the greedy choice property in this problem? I doubt the greedy
approach.
【在 k**********i 的大作中提到】
: DP的话应该也不是很快吧。。。我在careercup上看到有人用了greedy 写的
| o********r
发帖数: 79 | | s**9
发帖数: 207 | 8 DP可以这样解：
Let M(i) be the solution to d_1,...,d_i
Let w(i,j) be the weight of d_id_{i+1} or d_id_{i+1}d_{i+2}
M(i)=max{M(i-1), M(i-2)+w(i-1,i), M(i-3)+w(i-2,i)}
Greedy应该不行，因为M(i-3)+w(i-2,i) 可以比 M(i-1)大可以比M(i-1)小,例如1101和
0101的情况。
不知道分析的对不
,
030
【在 o********r 的大作中提到】
: from career cup.
: You are given a String number containing the digits of a
: phone number (the number of digits, n, can be any positive integer) . To
: help you memorize
: the number, you want to divide it into groups of contiguous digits. Each
: group must contain
: exactly 2 or 3 digits. There are three kinds of groups:
: • Excellent: A group that contains only the same digits. For example,
: 000 or 77.
: • Good: A group of 3 digits, 2 of which are the same. For example, 030
| a***9
发帖数: 364 | 9 有点奇怪为什么有M(i-1），不是每个组必须2个或者3个digit吗，你让i干嘛去？
【在 s**9 的大作中提到】
: DP可以这样解：
: Let M(i) be the solution to d_1,...,d_i
: Let w(i,j) be the weight of d_id_{i+1} or d_id_{i+1}d_{i+2}
: M(i)=max{M(i-1), M(i-2)+w(i-1,i), M(i-3)+w(i-2,i)}
: Greedy应该不行，因为M(i-3)+w(i-2,i) 可以比 M(i-1)大可以比M(i-1)小,例如1101和
: 0101的情况。
: 不知道分析的对不
:
: ,
: 030
| s**9
发帖数: 207 | 10 对，我理解错了。应该是
M(i)=max{M(i-2)+w(i-1,i), M(i-3)+w(i-2,i)}
Greedy应该还是不行，因为第一项可以比第二项大或者小,例如
01101 和
00101 的情况。
【在 a***9 的大作中提到】
: 有点奇怪为什么有M(i-1），不是每个组必须2个或者3个digit吗，你让i干嘛去？
| e**********6
发帖数: 78 | 11 感觉不能是M(i-1)吧，因为不可以1个为一组。感觉应该是
M(i)=MAX{M(i-2)+w(i-2,i),M(i-3)+w(i-3,i)}？ |
|
