问一个题 house paint - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个题 house paint

问一个题 house paint# JobHunting - 待字闺中

w*n2013-08-06 07:08

1 楼

就是前面某位拿了一堆Offer的大牛贴的
minimize the cost of painting K houses, each house has different
costs to paint in different colors,
2 houses (next to each other) cannot be painted in the same
color. DP 问题
请教怎么DP?
谢谢先!!

f*d2013-08-06 07:08

2 楼

只想出一个复杂度KC^2的dp
不知道KC可解否
K:#of house
C:#of colors

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

: 就是前面某位拿了一堆Offer的大牛贴的
: minimize the cost of painting K houses, each house has different
: costs to paint in different colors,
: 2 houses (next to each other) cannot be painted in the same
: color. DP 问题
: 请教怎么DP?
: 谢谢先!!

f*d2013-08-06 07:08

3 楼

可以优化到KClogC
还是不知道KC可解否~

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

: 只想出一个复杂度KC^2的dp
: 不知道KC可解否
: K:#of house
: C:#of colors

f*d2013-08-06 07:08

4 楼

嗯 O(KC)可解~

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

: 可以优化到KClogC
: 还是不知道KC可解否~

f*d2013-08-06 07:08

5 楼

dp[k][c]: the optimal solution of painting the first k houses where the
kth house is colored with color c.
dp[k-1][1, C] => dp[k][1, C] transition cost can be reduce to O(C)

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

w*n2013-08-06 07:08

6 楼

没太看懂
如果 dp[k-1][c] 是 paint K-1个house的最优解（cost最低），并且第k-1个house是
用颜色C
那么dp[k][x]里， x必须是跟C不一样的颜色。如果取颜色X, min(cost(x)) x!=C, 这
个不一定是k个house的最优解8

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

: dp[k][c]: the optimal solution of painting the first k houses where the
: kth house is colored with color c.
: dp[k-1][1, C] => dp[k][1, C] transition cost can be reduce to O(C)

f*d2013-08-06 07:08

7 楼

找到dp[k-1][1..C]里面最小的一个，并且计数, 如果最小的计数个数>1 ，那么，等不
等于C就无所谓了，如果最小的计数个数=1，再记录一个次小的即可~
错了请指出~

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

: 没太看懂
: 如果 dp[k-1][c] 是 paint K-1个house的最优解（cost最低），并且第k-1个house是
: 用颜色C
: 那么dp[k][x]里， x必须是跟C不一样的颜色。如果取颜色X, min(cost(x)) x!=C, 这
: 个不一定是k个house的最优解8