d******v
发帖数: 801 | 1 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。 |
u*a
发帖数: 247 | 2 两个机器人？
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
|
d******v
发帖数: 801 | 3 是啊，一个机器人就是leetcode原题了。
【在 u*a 的大作中提到】
: 两个机器人？
|
u*a
发帖数: 247 | 4 两个从同一个角出发么？走一遍把走过地方设为0，再走一遍不就完了。
【在 d******v 的大作中提到】
: 是啊，一个机器人就是leetcode原题了。
|
w****k
发帖数: 755 | 5 先求得最大值和路径，然后把路径上的单元都设为0，然后再来一遍，相加即可。有反
例么？ |
h****t
发帖数: 69 | 6 Counter example
0, 0, 2
0, 3, 2
0, 1, 0
greedy = (3 + 2) + 2 = 7
optimal = (3 + 1) + (2 + 2) = 8 |
l*******a
发帖数: 16 | |
r****7
发帖数: 2282 | 8 看成一个图，把两个机器人看成机器人从左上走到右下，再从右下走到左上这么一个路
径，找到最长的路径。
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
|
u*a
发帖数: 247 | 9 不能直接找吧。这不是一个静态的图，走过的格子被清零了。
【在 r****7 的大作中提到】
: 看成一个图，把两个机器人看成机器人从左上走到右下，再从右下走到左上这么一个路
: 径，找到最长的路径。
|
l********1
发帖数: 74 | |
|
|
r****7
发帖数: 2282 | 11 清不清零没影响，反正你也不能走同一个格子两次
【在 u*a 的大作中提到】
: 不能直接找吧。这不是一个静态的图，走过的格子被清零了。
|
u*a
发帖数: 247 | 12 Why not?
【在 r****7 的大作中提到】
: 清不清零没影响，反正你也不能走同一个格子两次
|
i*********e
发帖数: 21 | 13 钱的数量改成负数，然后求流量为2的最小费用流。再取负就是答案。 |
i*********e
发帖数: 21 | 14 话说回来，这是某人/某书上的变体还是真的有人面试时被问了？面试问费用流也算是
变态了。 |
h****t
发帖数: 69 | 15 The cost of minimum-cost flow problem is on the edges, not on the vertices. |
d******v
发帖数: 801 | 16 这是原来有人发过的g家面经
【在 i*********e 的大作中提到】
: 话说回来，这是某人/某书上的变体还是真的有人面试时被问了？面试问费用流也算是
: 变态了。
|
i*********e
发帖数: 21 | 17
不好意思，我略过了一些步骤。
把每个vertice分拆成两个vertice, create two edges between them, one with INF
capacity and 0 cost, one with capacity of 1 and cost of -money. Edges
between the original vertices stays the same, with 0 cost and INF capacity(
or capacity of 2, does not matter).
This is the standard way to move cost/capacity to edges.
【在 h****t 的大作中提到】
: The cost of minimum-cost flow problem is on the edges, not on the vertices.
|
h****t
发帖数: 69 | |
U***A
发帖数: 849 | |
f*********s
发帖数: 34 | 20 If there is one robot, it can be at each of m*n locations, with DP,
calculation needs to be done once only for each location so the time
complexity is O(m*n).
If there are two robots, they can be at each of (m*n)*(m*n) locations, again
with DP, calculation needs to be done once only for each location so the
time complexity is O(m*n*m*n). |
|
|
U***A
发帖数: 849 | 21 给个具体算法？
again
【在 f*********s 的大作中提到】
: If there is one robot, it can be at each of m*n locations, with DP,
: calculation needs to be done once only for each location so the time
: complexity is O(m*n).
: If there are two robots, they can be at each of (m*n)*(m*n) locations, again
: with DP, calculation needs to be done once only for each location so the
: time complexity is O(m*n*m*n).
|
j********g
发帖数: 80 | 22 int twoRobs(vector > &MP){
int M = MP.size();
int N = MP[0].size();
int P_LEN = M + N -1;
vector > dp1 = vector >(N, vector(N, 0));
vector > dp2 = vector >(N, vector(N, 0));
dp1[0][0] = MP[0][0];
dp2[0][0] = MP[0][0];
for (int p = 2; p <= P_LEN; p++){//p is the length of the path
for (int x1 = 0; x1 < N; x1++){
for (int x2 = x1; x2 < N; x2++){
int y1 = p - 1 - x1;
int y2 = p - 1 - x2;
if(y1<0 || y2<0 || y1>=M || y2>=M)
continue;
int best = 0;
int delta = MP[y1][x1];
if (x1 != x2)
delta += MP[y2][x2];
if(x1>0 && x2>0)//from left left
best = max(best, dp1[x1-1][x2-1] + delta);
if(x1>0 && y2>0)//from left up
best = max(best, dp1[x1-1][x2] + delta);
if(y1>0 && x2>0)//from up left
best = max(best, dp1[x1][x2-1] + delta);
if(y1>0 && y2>0)//from up up
best = max(best, dp1[x1][x2] + delta);
dp2[x1][x2] = best;
}
}
dp1=dp2;
}
return dp1[N-1][N-1];
} |
W*********y
发帖数: 481 | 23 传纸条模型
三维dp
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
|
d*******8
发帖数: 23 | 24 这就是一个二维动态规划的问题.
下面是我的代码链接和用 hlight 给的例子作为测试来验证的代码:
http://ideone.com/fnC3de |
a******u
发帖数: 69 | |
i****7
发帖数: 26 | |
