uva10003专题

例题9-9 UVa10003 Cutting Sticks(DP:矩阵链乘)

题意: 看白书 要点: 明显是类似于矩阵连乘问题,用d[i][j]标记i到j中的最优费用,从中间一点k处截成两半,可以写出状态转移方程为d[i][j] = min(d[i][j], d[i][k] + d[k][j] + pos[j] - pos[i]),不难看出这实际是一个区间DP问题,通过j-i小区间不断递增进行DP,注意这里i和j不用写成0~len,因为d[i][j]只是起到一个存储状