一道动规的题，求求大家帮帮我！！！急需这几天出答案

我刚注册，看看能不能发帖，能发就说点思路

zerowing444 发表于 2013-12-27 23:21
我刚注册，看看能不能发帖，能发就说点思路

就在这回复呢？

你这样想试试：从左往右一列一列考虑，在第一列，你可以什么都不做，可以竖着连下来，也可以在第1到4个track时候拐到下一列。这样一共6种情况，其中4种拐的情况会影响到下一列的考虑，你可以把从上一列拐过来的line想象成“必须处理的接口”，每个接口有三种处理方法：拐上去，拐下去，或连到下一列。这就是大概的思路了，但还有好多细节需要考虑，比如说有从上一列来的track3的接口，那你这一列如果要开一个新line的话就不能直接从A连到B了，只能有两种情况：新线路在track1拐或track2拐；再比如你从上一列收到两个接口，那么位置靠上那个接口在这一列的处理方法只能是向上拐或连到下一列，相对位置靠下的只能向下拐或连到下一列，如果三个或更多那么位于中间的就只能连到下一列。总之有挺多情况需要考虑。以上假设所有line只能从A开始。

我的拙见，思路不是很清晰，但希望能帮你扩展一下思路。

zerowing444 发表于 2013-12-27 23:50
你这样想试试：从左往右一列一列考虑，在第一列，你可以什么都不做，可以竖着连下来，也可以在第1到4个trac ...

谢谢你！不过也可以从B开始吧？

peikexin9 发表于 2013-12-28 00:15
谢谢你！不过也可以从B开始吧？

这就不知道了，你得问教授。如果可以从B开始的话就多几种情况，不过差不多。

zerowing444 发表于 2013-12-28 00:21
这就不知道了，你得问教授。如果可以从B开始的话就多几种情况，不过差不多。

是可以从B开始的，总之就是一个点和另一个点相连，就能够成一条线，可能直接划下去，也可能经过某个track转两次到两一个点

说下我的一点点思路吧，可能会对楼主有帮助,dp[i][j][mask]表示最后一个单条线的plan，一端在sideA的i处，另一端在sideB的j处，然后已经在mask表示的track集合转过弯，然后楼主可以枚举这个(i, j)可以转移到哪些新的i',j'，并且转弯处不会与mask集合有冲突，然后就是细节问题了

1guangnian 发表于 2013-12-28 05:32
说下我的一点点思路吧，可能会对楼主有帮助,dp[j][mask]表示最后一个单条线的plan，一端在sideA的i处，另一 ...

恩，我现在就是这么想的，主要是想想dp在最右那条单线该记录些什么信息就够了

1guangnian 发表于 2013-12-28 05:32
说下我的一点点思路吧，可能会对楼主有帮助,dp[j][mask]表示最后一个单条线的plan，一端在sideA的i处，另一 ...

谢谢你！

感谢各位！这道题在大家的帮助下我做出来了，用了一下状态压缩，想通了确实代码就几行，谢谢大家热心帮助！