google onsite

求第三题思路~

第四题应该怎么做啊，完全没有思路。==

说说自己第三题的思路：

先排序，然后用DP，DP里面有个贪心的地方，就是最后选出来的m个pair，每个pair里面的数在原有序数组里肯定是相连的，可用传统贪心的反证法证明这个。

然后就用DP找pair，trivial解O(mn)时间和空间，可以用技巧压到O(n)空间。

阿咧，打完之后，感觉跟楼主的思路重复了，楼主轻拍。

blood8088 发表于 2016-11-4 11:32
说说自己第三题的思路：

先排序，然后用DP，DP里面有个贪心的地方，就是最后选出来的m个pair，每个pair ...

我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是[i, i+1] 那么dp 转移方程为
dp[m][j][l] = min{max{dp[m1][j][i-1]}, dp[m2][i+1][l], diff(i, i+1)} (m1 + m2 = m-1)....
不过感觉复杂度不止o(mn)...
似乎可以继续优化。。。

achilleszou 发表于 2016-11-4 12:35
我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是 那么dp 转移方程为

貌似下面的dp 更简单。
dp[i][j] = min{dp[i][j-1], max{diff(j, j-1), dp[i-1][j-2]}

achilleszou 发表于 2016-11-4 12:41
貌似下面的dp 更简单。
dp[j] = min{dp[j-1], max{diff(j, j-1), dp[j-2]}

写错了，应该是：

dp[i][j] = min{dp[i][j-1], max{diff(j, j-1), dp[i-1][j-2]}

dp[i][j] 表示在 下标[0...j] 中取i对筷子。

achilleszou 发表于 2016-11-4 12:35
我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是 那么dp 转移方程为

我觉得是这样。

dp[m][i] = min( dp[m][i + 1],                                      ----> 不选 pair(i, i+1)
                         max(dp[m - 1][i + 2], diff(i, i+1))        ----> 选 pair(i, i+1)


补充内容 (2016-11-4 12:46):
打错，等式左边应该是 dp[m][i];

补充内容 (2016-11-4 12:47):
dp[m][  i  ]

blood8088 发表于 2016-11-4 12:45
我觉得是这样。

dp[m] = min( dp[m],                                      ----> 不选 pair(i, i+1) ...

你的dp 解法中 dp[m][i] 代表从 [i, ... n] 中 选m双筷子?

我的解法中 dp[m][i] 代表从[0, ... i] 中 选m双筷子。

如果我的理解没错的话，应该两个都行

achilleszou 发表于 2016-11-4 12:56
你的dp 解法中 dp[m] 代表从  中 选m双筷子?

我的解法中 dp[m] 代表从[0, ... i] 中 选m双筷子。

为啥发帖中 【】【】 被删了。。。。。==|

achilleszou 发表于 2016-11-4 12:57
为啥发帖中 【】【】 被删了。。。。。==|

[     i      ]


好像会被解释成斜体字(italic)，类似html什么的吧。