5689 - 动态规划：期望DP：走迷宫

一个R×C 的矩形网格。除了出口网格外，每个网格中都有一个传送门，每次使用传送门需要消耗 2 点魔力。位于网格G(r,c) 的传送门会将 AA 传送到以下位置之一： 下方的网格G(r+1,c)； 右侧的网格G(r,c+1)；

或者留在原地G(r,c)。 每种传送目标的概率由题目给出

AA 最初位于 地图 的左上角(1,1)，迷宫的出口位于右下角 (R,C)。给定每个传送门的传送概率，你的任务是帮助AA 计算她逃离 地图 所需的期望魔力值。

第一行输入2个整数R和C，表示网格的行和列； 接下来的R行，每行包含C * 3个实数，精确到小数点后两位。每三个数为一组。第R行第C组的第一个、第二个和第三个数分别表示位于网格(R,C)中的传送门传送到网格(R,C)、网格(R,C+1)、网格的概率(R+1,C)。两组数字之间用4个空格隔开。 可以确定的是，每组中的三个数之和为1，并且最右边各组的第二个数为0（因为它们右边没有网格），而最下面各组的第三个数为0（因为它们下面没有网格）。 你可以忽略输入数据中的最后三个数。打印它们只是为了格式看起来整齐。 答案保证不大于1000000。 在文件结束（EOF）时结束输入 。

一个精确到小数点后三位（四舍五入）的实数，表示离开矩阵需要的期望魔力值

R,C小于1000