一道动态规划题，不过似乎可以用回溯水过去，回溯的话效率很烂的。 13988658 10003 Cutting Sticks Accepted C++ 1.882 2014-08-04 09:26:49 AC代码： #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include

题目链接：https://vjudge.net/problem/19208/origin 题目大意： 对于一个a*b和b*c的矩阵相乘的结果为a*b*c， 如果有三个矩阵相乘就是a*b b*c c*d 这三个矩阵相乘，因为满足结合律，所以可以先乘后两个，再和第一个相乘。由于先乘那一对矩阵决定了运算量的大小，所以让你计算怎么结合相乘能使得运算量最小。 那么什么是运算量的大小呢：比如有三个矩阵为

// uva348 最优矩阵链乘// 典型的区间dp// dp[i][j] 表示矩阵i到j链乘所得到的最小花费// dp[i][j] = min(dp[i][k]+dp[k+1][j]+a[i].pl*a[k].pr*a[j].pr);// 在区间i到j上找一个k使得dp[i][k]+dp[k+1][j]这两部分的和在加上最后的// a[i].pl*a[k].pr*p[i].pr的最小值

348 - Optimal Array Multiplication Sequence Time limit: 3.000 seconds  http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=284 记忆化搜索：dp[a]

题意： 看白书 要点： 明显是类似于矩阵连乘问题，用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]只是起到一个存储状