p*****2
发帖数: 21240 | 1 下个月要面某国DP大赛第一名的选手。估计要把我秒杀了。 |
w****x
发帖数: 2483 | 2 DP大赛？？？
dynamic programming还专门有个大赛？ |
p*****2
发帖数: 21240 | 3
某国有。至少简历上是这样写的。
【在 w****x 的大作中提到】
: DP大赛？？？
: dynamic programming还专门有个大赛？
|
k***x
发帖数: 6799 | 4 是咖喱国么？
【在 p*****2 的大作中提到】
:
: 某国有。至少简历上是这样写的。
|
p*****2
发帖数: 21240 | 5
邻国
【在 k***x 的大作中提到】
: 是咖喱国么？
|
t*********h
发帖数: 941 | 6 求大赛名称
【在 p*****2 的大作中提到】
: 下个月要面某国DP大赛第一名的选手。估计要把我秒杀了。
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 8
All XXX Dynamic Programming Competition
【在 t*********h 的大作中提到】
: 求大赛名称
|
O******i
发帖数: 269 | 9 这个不错，能检验成分。
【在 p*****2 的大作中提到】
: 大家帮我想想出什么题。张弛那道怎么样？
|
g*********e
发帖数: 14401 | |
|
|
d**********n
发帖数: 132 | |
p*****2
发帖数: 21240 | 12
好。一直自己没做。这次正好有个机会自己做一遍了。
【在 O******i 的大作中提到】
: 这个不错，能检验成分。
|
a***o
发帖数: 1182 | 13 张弛是什么题目？二爷布道啊
【在 p*****2 的大作中提到】
: 大家帮我想想出什么题。张弛那道怎么样？
|
c********t
发帖数: 5706 | 14 我上次面试碰到leetcode上分金币那道题，因为那时候没看leetcode,直接被撂倒了。
其实那题动态方程很难想出来
【在 p*****2 的大作中提到】
: 下个月要面某国DP大赛第一名的选手。估计要把我秒杀了。
|
a***o
发帖数: 1182 | 15 这么变态，哪个公司要这个的dp？
【在 c********t 的大作中提到】
: 我上次面试碰到leetcode上分金币那道题，因为那时候没看leetcode,直接被撂倒了。
: 其实那题动态方程很难想出来
|
w****x
发帖数: 2483 | 16
哪个分金币？？
【在 c********t 的大作中提到】
: 我上次面试碰到leetcode上分金币那道题，因为那时候没看leetcode,直接被撂倒了。
: 其实那题动态方程很难想出来
|
c********t
发帖数: 5706 | 17 ft,现在leetcode down了，找不到了。
【在 w****x 的大作中提到】
:
: 哪个分金币？？
|
k***x
发帖数: 6799 | 18 这个么？
http://leetcode.com/2011/02/coins-in-line.html
【在 c********t 的大作中提到】
: ft,现在leetcode down了，找不到了。
|
p*****2
发帖数: 21240 | 19
靠。太神奇了。第一次做，竟然一次pass。
【在 p*****2 的大作中提到】
:
: 好。一直自己没做。这次正好有个机会自己做一遍了。
|
p*****2
发帖数: 21240 | 20
scrambled string
【在 a***o 的大作中提到】
: 张弛是什么题目？二爷布道啊
|
|
|
p*****2
发帖数: 21240 | 21
你说的是OJ上边的吗？上边貌似就一题，不算难题。
【在 c********t 的大作中提到】
: 我上次面试碰到leetcode上分金币那道题，因为那时候没看leetcode,直接被撂倒了。
: 其实那题动态方程很难想出来
|
B*******1
发帖数: 2454 | 22 我上周刚做的这题不错，起码我想不出来，我就做出了div2的version
http://community.topcoder.com/stat?c=problem_statement&pm=12350
【在 p*****2 的大作中提到】
:
: 你说的是OJ上边的吗？上边貌似就一题，不算难题。
|
p*****2
发帖数: 21240 | 23
你现在做topcoder呀。钛膜拜了。你这么牛都做不出来，那不是太难为那个冠军了吗。
【在 B*******1 的大作中提到】
: 我上周刚做的这题不错，起码我想不出来，我就做出了div2的version
: http://community.topcoder.com/stat?c=problem_statement&pm=12350
|
p*****2
发帖数: 21240 | |
B*******1
发帖数: 2454 | 25 dp比你差远了啊。
★ 发自iPhone App: ChineseWeb 7.7
【在 p*****2 的大作中提到】
:
: 把题解放到博客里了。http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
|
g****x
发帖数: 223 | 26 DP的一个小小的应用是HMM。楼主不妨一试，即考了DP，编成，又考了概率，如果对方
答不出，楼主又可以显示自己高深的理论数学功底，让他崇拜吧。这年头，想考倒一个
人还不容易？DP不成，咱们可以来LP，LP不成，再来数论或FFT，。。。MIT的大白书上
有的是这样的题。再不成，自己读读SODA／STOC上的文章，然后去考人，让他３０分钟
内提出个大概想法，如果想不出，证明此人＂CANNOT THINK LOUDLY＂。
【在 p*****2 的大作中提到】
: 下个月要面某国DP大赛第一名的选手。估计要把我秒杀了。
|
p*****2
发帖数: 21240 | 27
HMM是啥东西呀？你说的这些我全不懂，怎么考人呀。
【在 g****x 的大作中提到】
: DP的一个小小的应用是HMM。楼主不妨一试，即考了DP，编成，又考了概率，如果对方
: 答不出，楼主又可以显示自己高深的理论数学功底，让他崇拜吧。这年头，想考倒一个
: 人还不容易？DP不成，咱们可以来LP，LP不成，再来数论或FFT，。。。MIT的大白书上
: 有的是这样的题。再不成，自己读读SODA／STOC上的文章，然后去考人，让他３０分钟
: 内提出个大概想法，如果想不出，证明此人＂CANNOT THINK LOUDLY＂。
|
B*******1
发帖数: 2454 | 28 hidden markov model?
http://blog.csdn.net/skyline0623/article/details/8197478
【在 p*****2 的大作中提到】
:
: HMM是啥东西呀？你说的这些我全不懂，怎么考人呀。
|
c********t
发帖数: 5706 | 29 你们还能上leetcode?
我怎么上不了 404 error如下。
Not Found
The requested URL /2011/02/coins-in-line.html was not found on this server.
Additionally, a 404 Not Found error was encountered while trying to use an
ErrorDocument to handle the request.
【在 k***x 的大作中提到】
: 这个么？
: http://leetcode.com/2011/02/coins-in-line.html
|
p*****2
发帖数: 21240 | 30
你哪里有问题吧。新浪也上不了
【在 c********t 的大作中提到】
: 你们还能上leetcode?
: 我怎么上不了 404 error如下。
: Not Found
: The requested URL /2011/02/coins-in-line.html was not found on this server.
: Additionally, a 404 Not Found error was encountered while trying to use an
: ErrorDocument to handle the request.
|
|
|
c********t
发帖数: 5706 | 31 对啊，原来是我自己的问题啊，我重启试试
【在 p*****2 的大作中提到】
:
: 你哪里有问题吧。新浪也上不了
|
c********t
发帖数: 5706 | 32 二爷不知不觉已成第二个张弛
这次要和国内强人上演巅峰对决啊
【在 p*****2 的大作中提到】
:
: 你哪里有问题吧。新浪也上不了
|
c********t
发帖数: 5706 | 33 不是，我上不去，应该是前面兄弟说的这道吧
http://leetcode.com/2011/02/coins-in-line.html
【在 p*****2 的大作中提到】
:
: 你哪里有问题吧。新浪也上不了
|
p*****2
发帖数: 21240 | 34
这个还没做过。初步看需要存sum[i][j]
这样
dp[i][j]=max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])
一会儿做做
【在 c********t 的大作中提到】
: 不是，我上不去，应该是前面兄弟说的这道吧
: http://leetcode.com/2011/02/coins-in-line.html
|
p*****2
发帖数: 21240 | 35
张弛是神。这些题对他来说都是小意思。
【在 c********t 的大作中提到】
: 二爷不知不觉已成第二个张弛
: 这次要和国内强人上演巅峰对决啊
|
b*****n
发帖数: 482 | 36 想了个思路，不知道对不对：
1. 当前sum of dread大于当前怪物dread，可以直接过关
if dread[i+1] <= dp[i], dp[i+1] = dp[i]; total price no change.
2. 当前sum of dread小于当前怪物dread，怪物price为1，则进行收买，因为其性价比
最高。
if dread[i+1] > dp[i], price[i+1] = 1, dp[i+1] = dp[i] + dread[i+1]; total
price++.
3. 当前sum of dread小于当前怪物dread，怪物price为2, 则先寻找0~i中price为1的
还没有被pick的最大dread，如果bribe它后sum of dread大于当前怪物dread，则收买
之，total price加1；如果不存在这样的怪物，则收买当前怪物，total price加2。
if dread[i+1] > dp[i], price[i+1] = 2, dp[i+1] = dp[i] + {max(dread[k],
where k dread[i+1] && price[k
] == 1), or dread[i+1] if dread[k] not available}； total price+1或+2 based
on whether dread[k] or dread[i+1] is picked.
【在 B*******1 的大作中提到】
: 我上周刚做的这题不错，起码我想不出来，我就做出了div2的version
: http://community.topcoder.com/stat?c=problem_statement&pm=12350
|
