I will buy back USD at 1.027 today with CAD# Stock
d*v
1 楼
一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
k*n
2 楼
good luck all!
u*a
3 楼
两个机器人？
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
d*v
4 楼
是啊，一个机器人就是leetcode原题了。
【在 u*a 的大作中提到】
: 两个机器人？
【在 u*a 的大作中提到】
: 两个机器人？
u*a
5 楼
两个从同一个角出发么？走一遍把走过地方设为0，再走一遍不就完了。
【在 d******v 的大作中提到】
: 是啊，一个机器人就是leetcode原题了。
【在 d******v 的大作中提到】
: 是啊，一个机器人就是leetcode原题了。
w*k
6 楼
先求得最大值和路径，然后把路径上的单元都设为0，然后再来一遍，相加即可。有反
例么？
例么？
h*t
7 楼
Counter example
0, 0, 2
0, 3, 2
0, 1, 0
greedy = (3 + 2) + 2 = 7
optimal = (3 + 1) + (2 + 2) = 8
0, 0, 2
0, 3, 2
0, 1, 0
greedy = (3 + 2) + 2 = 7
optimal = (3 + 1) + (2 + 2) = 8
l*a
8 楼
分成上下三角分开走？
r*7
9 楼
看成一个图，把两个机器人看成机器人从左上走到右下，再从右下走到左上这么一个路
径，找到最长的路径。
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
径，找到最长的路径。
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
u*a
10 楼
不能直接找吧。这不是一个静态的图，走过的格子被清零了。
【在 r****7 的大作中提到】
: 看成一个图，把两个机器人看成机器人从左上走到右下，再从右下走到左上这么一个路
: 径，找到最长的路径。
【在 r****7 的大作中提到】
: 看成一个图，把两个机器人看成机器人从左上走到右下，再从右下走到左上这么一个路
: 径，找到最长的路径。
l*1
11 楼
3维DP
r*7
12 楼
清不清零没影响，反正你也不能走同一个格子两次
【在 u*a 的大作中提到】
: 不能直接找吧。这不是一个静态的图，走过的格子被清零了。
【在 u*a 的大作中提到】
: 不能直接找吧。这不是一个静态的图，走过的格子被清零了。
u*a
13 楼
Why not?
【在 r****7 的大作中提到】
: 清不清零没影响，反正你也不能走同一个格子两次
【在 r****7 的大作中提到】
: 清不清零没影响，反正你也不能走同一个格子两次
i*e
14 楼
钱的数量改成负数，然后求流量为2的最小费用流。再取负就是答案。
i*e
15 楼
话说回来，这是某人/某书上的变体还是真的有人面试时被问了？面试问费用流也算是
变态了。
变态了。
h*t
16 楼
The cost of minimum-cost flow problem is on the edges, not on the vertices.
d*v
17 楼
这是原来有人发过的g家面经
【在 i*********e 的大作中提到】
: 话说回来，这是某人/某书上的变体还是真的有人面试时被问了？面试问费用流也算是
: 变态了。
【在 i*********e 的大作中提到】
: 话说回来，这是某人/某书上的变体还是真的有人面试时被问了？面试问费用流也算是
: 变态了。
i*e
18 楼
不好意思，我略过了一些步骤。
把每个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
19 楼
多谢，受教了。这个面试题未免太难了点。
U*A
20 楼
有没有人给个算法。
f*s
21 楼
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).
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
22 楼
给个具体算法？
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).
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
23 楼
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];
}
int M = MP.size();
int N = MP[0].size();
int P_LEN = M + N -1;
vector
vector
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
24 楼
传纸条模型
三维dp
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
三维dp
【在 d******v 的大作中提到】
: 一个m*n的matrix每个格子上放一定数量的钱，机器人走过一个格子就把钱拿走，从左
: 上角走到右下角，只能向下向右走。求出两个机器人能拿到的钱的总和最大值。
d*8
25 楼
这就是一个二维动态规划的问题.
下面是我的代码链接和用 hlight 给的例子作为测试来验证的代码:
http://ideone.com/fnC3de
下面是我的代码链接和用 hlight 给的例子作为测试来验证的代码:
http://ideone.com/fnC3de
i*7
27 楼
相关阅读
轻松一下牛牛们进场吧，今天跌300点！求sharebulider 的free trade或者automatic trade code今晚预测里有个股票预测说会起18到32元How can CNBC issue this kind of news to persuade the people to sell stocks?如果百度跌到80，只跌5% 的股票都笑了报税求助！bidu居然被拉起来了罗斯福曾经说过:“恐惧就是恐惧本身” 明天会更好！！！！！bloody百度竞价排名现在占收益的多少？QIHU should be up today no matter how much the market goes downSina Corp Cut To Neutral From Outperform By Credit Suisse?sweat a lot after running 6000 meter黄金跟Dow的关系为啥没人讨论google呢？能捞吗？goldcoin 大虾， bidu明天又没有也能反弹回135？time to short VXX新浪的后台是四代核吗？