贡献F家Onsite一题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献F家Onsite一题

贡献F家Onsite一题# JobHunting - 待字闺中

s*l2013-08-22 07:08

1 楼

见过的题目就不说了，说个没见过的，基本是这题把俺放倒了，大牛们可以看看怎么做
。
河对岸有两排数量相等的城市。
a1 a2 a3 a4.....an
-------------------
-------------------
b1 b2 b3 b4.....bn
每个城市ai都有对应的友好城市bj. 比如(a1, b3), (a2, b1), (a3, b2)...
问题是如果姐妹城市之间可以互相建桥，但是这些桥之间不能交叉，给定这些姐妹城市
的mapping，最多可以建多少个桥？

s*y2013-08-22 07:08

2 楼

什么叫给定mapping？
目测是图论问题。planer graphs。可能是结论直接用就可以了。

a*u2013-08-22 07:08

3 楼

dp，跟longest common subsequence一个思路

z*c2013-08-22 07:08

4 楼

这个要用贪婪算法吧，感觉和排时间表很像
先找出最靠左边的一组(Ai,Bj)，然后相同方法找下一组A[max(i,j)+1],B[max(i,j)+1]
至于怎么找到最左边的，目前想到的是可以按照max(Ai,Bj)排序

A*o2013-08-22 07:08

5 楼

a_i 到 b_j是一一对应吗？
感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

【在 s*****l 的大作中提到】

: 见过的题目就不说了，说个没见过的，基本是这题把俺放倒了，大牛们可以看看怎么做
: 。
: 河对岸有两排数量相等的城市。
: a1 a2 a3 a4.....an
: -------------------
: -------------------
: b1 b2 b3 b4.....bn
: 每个城市ai都有对应的友好城市bj. 比如(a1, b3), (a2, b1), (a3, b2)...
: 问题是如果姐妹城市之间可以互相建桥，但是这些桥之间不能交叉，给定这些姐妹城市
: 的mapping，最多可以建多少个桥？

s*l2013-08-22 07:08

6 楼

回楼上的，给定mapping就是说给定这些a和b的友好城市关系了。
ai到bj是一一对应的

s*52013-08-22 07:08

7 楼

用greedy怎么样？先看所有pair都建桥的话，有多少个交叉。然后remove那个能最大限
度减少交叉次数的桥，重复此过程直到没有交叉为止。
不过不能保证就是最佳结果。
可能要用DP？不过不知怎么搞。

l*o2013-08-22 07:08

8 楼

看到最大先想到dp
f[i,j] = max{f[i - 1, j], f[i, j - 1]} + 1 (if [i,j] has mapping)
还能降一维空间。
瞎想的，可能不对。

s*52013-08-22 07:08

9 楼

实在看不出怎么一样法。

【在 a*****u 的大作中提到】

: dp，跟longest common subsequence一个思路

a*u2013-08-22 07:08

10 楼

你这个跟我说的方法都是对的。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

a*u2013-08-22 07:08

11 楼

longest common subsequence里的两char相等，对应这道题的两城市有mapping

【在 s***5 的大作中提到】

: 实在看不出怎么一样法。

a*u2013-08-22 07:08

12 楼

我刚刚说错了，是subsequence，不是substring

【在 s***5 的大作中提到】

: 实在看不出怎么一样法。

c*d2013-08-22 07:08

13 楼

哇这个解法妙。
如果推广到每个城市可以有多个友好城市，那似乎就只能dp了。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

i*o2013-08-22 07:08

14 楼

非一一对应也行
这问题比较有意思

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

s*52013-08-22 07:08

15 楼

这个很好理解，很不错。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

z*c2013-08-22 07:08

16 楼

排序方法好巧妙

r*e2013-08-22 07:08

17 楼

mit的那个dp讲解里有这道题，连桥和城市的说服都一样。

【在 s*****l 的大作中提到】

g*92013-08-22 07:08

18 楼

贴个DP的完整代码给大家讨论，测了几个case感觉是对的解法，简单原理：
假设a1,a2 ... an 和 b1,b2...bn 都在 1.. n之间，便于讨论
table[i][j] 表示了只包含从 a1..ai 到 b1..bj 作为桥端点的结果
rev 是逆向映射。
DP是假设了ai bj是一一对应，不知道有重复映射的话，怎么做比较好？
有么有人能贴个排序的代码？谢谢
#include
#include
#include
using namespace std;
int MaxBridge(map &bridge, int n) {
map rev;
for (auto b : bridge) {
rev[b.second] = b.first;
}
vector> table(n+1, vector(n+1));
int i, j, t, a;
for (j = 0; j <= n; j++) {
table[0][j] = 0;
}
for (i = 0; i <= n; i++) {
table[i][0] = 0;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
a = table[i-1][j-1];
if (bridge.count(i)) {
t = bridge[i];
if (t <= j) {
a = std::max(a, table[i-1][t-1]+1);
}
}
if (rev.count(j)) {
t = rev[j];
if (t <= i) {
a = std::max(a, table[t-1][j-1]+1);
}
}
table[i][j] = a;
}
}
return table[n][n];
}
void Test() {
int n;
n = 6;
map m;
m[1] = 3;
m[2] = 1;
m[3] = 6;
m[4] = 2;
m[6] = 4;
cout << MaxBridge(m, n) << endl;

m.clear();
n = 5;
m[1] = 1;
m[2] = 2;
m[3] = 3;
m[4] = 4;
m[5] = 5;
cout << MaxBridge(m, n) << endl;

m.clear();
n = 5;
m[1] = 5;
m[5] = 1;
m[2] = 2;
cout << MaxBridge(m, n) << endl;
return;
}
int main() {
Test();
return 0;
}