a*i
2 楼
【 以下文字转载自 Living 讨论区 】
发信人: anweiwei (谁是我是谁), 信区: Living
标 题: 猫抓沙发,请教沙发翻新的问题
发信站: BBS 未名空间站 (Mon Jun 7 11:36:32 2010, 美东)
我家沙发没买多长时间，因为布料没有挑选恰当，现在沙发边缘的地方已经被我家猫猫
抓得惨不忍睹了。
我不知道纽约或者新泽西地区有没有类似的沙发翻新服务，就是可以沙发整个换一种布
料? 谁如果知道,麻烦推荐一下.
不胜感激!
发信人: anweiwei (谁是我是谁), 信区: Living
标 题: 猫抓沙发,请教沙发翻新的问题
发信站: BBS 未名空间站 (Mon Jun 7 11:36:32 2010, 美东)
我家沙发没买多长时间，因为布料没有挑选恰当，现在沙发边缘的地方已经被我家猫猫
抓得惨不忍睹了。
我不知道纽约或者新泽西地区有没有类似的沙发翻新服务，就是可以沙发整个换一种布
料? 谁如果知道,麻烦推荐一下.
不胜感激!
a*7
3 楼
是不是上课很累啊
l*a
4 楼
还有什么条件吗？
每次允许取的值有没有什么限制
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
每次允许取的值有没有什么限制
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
u*g
5 楼
帮顶，同时请教如何让猫不抓沙发？？？
s*g
6 楼
律师有赚钱多的,也有落魄赚钱少的.(现在law school毕业的大概找到工作的在~50%??
自己去查吧)
专利律师也要写作好的.
(一般律师的话,能说违心话吗?能,就去!)
但也有转专利律师干的好的,人际交往/写作都要棒!
自己去查吧)
专利律师也要写作好的.
(一般律师的话,能说违心话吗?能,就去!)
但也有转专利律师干的好的,人际交往/写作都要棒!
i*d
7 楼
DP
max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
如果只是以拿得比对方多为目的，就简单一些
如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
如果n是奇数，要多算一步
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
如果只是以拿得比对方多为目的，就简单一些
如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
如果n是奇数，要多算一步
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
p*f
8 楼
沙发边上放一个让她更喜欢磨爪的东西。
【在 u********g 的大作中提到】
: 帮顶，同时请教如何让猫不抓沙发？？？
【在 u********g 的大作中提到】
: 帮顶，同时请教如何让猫不抓沙发？？？
h*t
9 楼
来不及了，除非你对美国政治历史海洋法系法理有足够的基础。
否则，想都别想
否则，想都别想
t*d
10 楼
啥意思？有多少取多少，拿光了不就最多了吗。
a*y
12 楼
两个人轮着拿吧
【在 t**d 的大作中提到】
: 啥意思？有多少取多少，拿光了不就最多了吗。
【在 t**d 的大作中提到】
: 啥意思？有多少取多少，拿光了不就最多了吗。
b*s
13 楼
嗯，dp
l*a
14 楼
求解释。
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
n*y
15 楼
假定知道了max[2,n]和max[1,n-1]
取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
（这是从头取） 或者 （从另外一边取）
取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
（这是从头取） 或者 （从另外一边取）
d*2
16 楼
Can you explain what a[1~n] means? If it is sum, does not look right.
On the other hand, your non-DP algo (i.e. 如果只是以拿得比对方多为目的，就简
单一些...) seems to be the right answer, considering your opponent is trying
to max his return.
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
On the other hand, your non-DP algo (i.e. 如果只是以拿得比对方多为目的，就简
单一些...) seems to be the right answer, considering your opponent is trying
to max his return.
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
h*k
17 楼
似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
拿到的最优解，即所能拿到的最多面值；
sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
结束条件max(i,i+1) = max(a(i),a(i+1))
【在 n********y 的大作中提到】
: 假定知道了max[2,n]和max[1,n-1]
: 取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
: （这是从头取） 或者 （从另外一边取）
拿到的最优解，即所能拿到的最多面值；
sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
结束条件max(i,i+1) = max(a(i),a(i+1))
【在 n********y 的大作中提到】
: 假定知道了max[2,n]和max[1,n-1]
: 取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
: （这是从头取） 或者 （从另外一边取）
l*c
18 楼
ibread是对的.
a[1~n]是所有金币的总和. a[1~n]-max[2,n]就是你取a[1],你的对手只能取剩下的.
a[1~n]-max[1,n-1]就是你取走a[n].
偶数个金币的排列肯定是
奇偶奇偶。。。。。奇偶
你选了奇/偶的金币，对手只能选偶/奇的。所以可以用这个简单的策略。
类似上面的方法可以决定最佳方法，不过没有办法保证比对方拿的多
a[1~n]是所有金币的总和. a[1~n]-max[2,n]就是你取a[1],你的对手只能取剩下的.
a[1~n]-max[1,n-1]就是你取走a[n].
偶数个金币的排列肯定是
奇偶奇偶。。。。。奇偶
你选了奇/偶的金币，对手只能选偶/奇的。所以可以用这个简单的策略。
类似上面的方法可以决定最佳方法，不过没有办法保证比对方拿的多
n*y
19 楼
或者写成下面这样子更好理解一点
a[1] + max[3, n]
a[1] + max[2, n-1]
max [1,n] = max a[n] + max[1, n-2]
a[n] + max[2, n-1]
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
a[1] + max[3, n]
a[1] + max[2, n-1]
max [1,n] = max a[n] + max[1, n-2]
a[n] + max[2, n-1]
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
h*g
20 楼
请问为什么要分奇数和偶数来算啊？
为什么奇数要多算一步啊
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
为什么奇数要多算一步啊
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
i*e
21 楼
我的公式是：
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
i*e
22 楼
如果硬币个数为偶数的话，就如 lilacc 和 ibread 所说的，只要比较奇数位置硬币之
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
i*e
23 楼
你这 dp 公式跟我是一样的：
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1))，
然后 base case 为 max(i, j) = A[i], when i == j
可以用递归两行代码搞定，如果要提高效率的话用二维数组当缓冲，以免重复计算。
其实根本不需要这个公式来计算，直接计算硬币偶数位置的和，还有硬币奇数位置的和
，哪一个大就是答案了。（如果硬币个数是奇数的话，算多一步就知道答案了）。这是
因为对手也是聪明的，那他也会用同样的策略，所以对手的每一步都是可以预知的，所
以不需要 dp 公式来计算。
那如果把问题换为：
我先拿硬币，假设对手非常笨（尽量使得我拿到最多的硬币总值），那我最多能拿多少
呢？
这问题就要用 dp 来解了。
大家来探讨下思路吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1))，
然后 base case 为 max(i, j) = A[i], when i == j
可以用递归两行代码搞定，如果要提高效率的话用二维数组当缓冲，以免重复计算。
其实根本不需要这个公式来计算，直接计算硬币偶数位置的和，还有硬币奇数位置的和
，哪一个大就是答案了。（如果硬币个数是奇数的话，算多一步就知道答案了）。这是
因为对手也是聪明的，那他也会用同样的策略，所以对手的每一步都是可以预知的，所
以不需要 dp 公式来计算。
那如果把问题换为：
我先拿硬币，假设对手非常笨（尽量使得我拿到最多的硬币总值），那我最多能拿多少
呢？
这问题就要用 dp 来解了。
大家来探讨下思路吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
i*e
24 楼
终于把这题研究明白了，而且找到自己错在哪里，希望以下的总结对各位有帮助.
的和，哪一个大就是答案了。
刚刚发现一个 counter example 证明以上的说法是错的.
举例：
{3,2,2,3,1,2}
这时候第一个拿硬币的人最多可以拿到 8 的总值。（不管对手采取什么策略）
第一步拿左 3，这时候对手可以选择拿左 2 或右 2.
-- 如果对手拿左 2，我就拿右 2，剩下 {2,3,1}. 最后的 3 我是吃定的了。总值
为 8.
-- 如果对手拿右 2，我就拿左 2，剩下 {2,3,1}. 最后的 3 我也是吃定了。总值
也为 8.
所以，不管对手采取什么策略，我都能保证我最多能拿 8（假设对手是聪明的）.
如果算偶数位置的总值（7）和奇数位置的总值（6），这样虽然获胜，但不能保证能拿
到最大的硬币总值。当硬币个数为偶数时，这策略能保证绝对不输（但有可能打平）
但是，当硬币个数为奇数的时候就不能用以上的策略。当我拿了第一枚硬币之后，硬币
个数就成为偶数了。对手并不一定会使用以上的策略。所以，要寻找你所能拿到最大的
硬币总值，必须使用 DP 来解。
公式为：(where P(i,j) denotes the maximum amount of coins you can get
between location i and j (inclusive))
P(i,j) = max{ sum(i,j)-P(i+1,j), sum(i,j)-P(i,j-1) }，
可以把以上公式简化为：
P(i,j) = sum(i,j) - min{ P(i+1,j), P(i,j-1) },
P(i,i) = A[i] as base case.
另一个思路（不需要计算 sum(i,j)）的 DP 公式为：
P(i,j) = max{ A[i] + min{ P(i+2,j), P(i+1,j-1) },
A[j] + min{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
以上思路讲解请参考：
http://people.csail.mit.edu/bdean/6.046/dp/
如果把问题转换为对手非常笨的话，使得你最后能拿最大的总值，把上面的 DP 公式换
一换就行了：
P(i,j) = max{ A[i] + max{ P(i+2,j), P(i+1,j-1) },
A[j] + max{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
的和，哪一个大就是答案了。
刚刚发现一个 counter example 证明以上的说法是错的.
举例：
{3,2,2,3,1,2}
这时候第一个拿硬币的人最多可以拿到 8 的总值。（不管对手采取什么策略）
第一步拿左 3，这时候对手可以选择拿左 2 或右 2.
-- 如果对手拿左 2，我就拿右 2，剩下 {2,3,1}. 最后的 3 我是吃定的了。总值
为 8.
-- 如果对手拿右 2，我就拿左 2，剩下 {2,3,1}. 最后的 3 我也是吃定了。总值
也为 8.
所以，不管对手采取什么策略，我都能保证我最多能拿 8（假设对手是聪明的）.
如果算偶数位置的总值（7）和奇数位置的总值（6），这样虽然获胜，但不能保证能拿
到最大的硬币总值。当硬币个数为偶数时，这策略能保证绝对不输（但有可能打平）
但是，当硬币个数为奇数的时候就不能用以上的策略。当我拿了第一枚硬币之后，硬币
个数就成为偶数了。对手并不一定会使用以上的策略。所以，要寻找你所能拿到最大的
硬币总值，必须使用 DP 来解。
公式为：(where P(i,j) denotes the maximum amount of coins you can get
between location i and j (inclusive))
P(i,j) = max{ sum(i,j)-P(i+1,j), sum(i,j)-P(i,j-1) }，
可以把以上公式简化为：
P(i,j) = sum(i,j) - min{ P(i+1,j), P(i,j-1) },
P(i,i) = A[i] as base case.
另一个思路（不需要计算 sum(i,j)）的 DP 公式为：
P(i,j) = max{ A[i] + min{ P(i+2,j), P(i+1,j-1) },
A[j] + min{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
以上思路讲解请参考：
http://people.csail.mit.edu/bdean/6.046/dp/
如果把问题转换为对手非常笨的话，使得你最后能拿最大的总值，把上面的 DP 公式换
一换就行了：
P(i,j) = max{ A[i] + max{ P(i+2,j), P(i+1,j-1) },
A[j] + max{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
相关阅读
求human genetics/medical genetics方向审稿，谢谢万年生物泼石岛看了Jurassic World 内牛满面。。。 (转载)哪个公司的elisa kit便宜点申请了Technician的职位，老板觉得我Motivation不够，不够smart。PNAS投稿一问能源，环境，化工，生态，地学等国内外SCI交流审稿群410413283等待您的加入审稿机会 coronary artery diseases恶性神经内分泌肿瘤在哪治疗最好？UCSF opening for a bioinformatician/computational biologist这种情况能找到博后吗？auxin origin问个PCR-SEQ的技术问题Miltenyl cell separation columns-------Re-use???如何比较快速简单地把cDNA给做成dsDNA?【供求】波士顿一大房带卫生间出租 (转载)延过的OPT明年年底才到期，能不能提前转成H1bGeneric 药厂scientist的职业发展 (转载)有没有好点的免疫方面的书籍推荐？国内海外及港澳学者合作研究基金项目是搞笑吗与这两位比，施一公是业界良心