画廊 蓝桥杯/dp

从中点出发，到达左右的所有地方，最后回到终点的中点。

动态规划，注意初始化，计算浮点数时的问题

 从中点出发，到达左右的所有地方，最后回到终点的中点。

动态规划，注意初始化，计算浮点数时的问题

定义：dp[i][j][k]表示处理到左边第i个，右边第j个，当前位置在k的情况。k只有2个值，0为在左，1为在右。

状态转移:

        1、处理dp[i][j][0]： 此时状态的含义：1、在左边 2、i是即将要处理的 。3、j位置已经处理过了。 只能从左边下面一个转移过来，或者是从右边横过来（从已处理的状态转移过来）；但注意，不可能从右下或者是右上过来。从dp的定义看，是【已处理】，如果右下过来，就不算是处理到第j个了；对于后者，表象考虑的其实是右边走的快再转到左边的情况，但实际上，因为j在第二层for，所以对于左边的一个点i，实际上是从右边所有的点（all j）转移过来的，在此基础上取最值。即保证了所有情况都已经被处理，单个选择最优，总体必为最优

        2、处理dp[i][j][1]：相同

        3、初始化：单边走，不从另一边走过来的情况下总的距离；第一个点需要进行sqrt（a*a+b*b）；同时，当前位置的另一边应是无效状态，要把其改为0x3f3f3f3f。同时因为w要除以2，要么在一开始读值的时候保证w是double，要么在计算的时候进行手动强转，否则不准。

总代码：