POJ 1651 Multiplication Puzzle——dp

POJ 1651 Multiplication Puzzle——dp

类似于最优矩阵链乘的区间dp，定义dp[i][j]为区间【i，j】的元素除了头尾都被拿走这个状态下的最小总和，边界就是长度为2的区间初始化为0，这样转移方程就很好写了

#include #include #include #include using namespace std;const int maxn = 200;const int INF = 0x3f3f3f3f;int n, a[maxn], dp[maxn][maxn];int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i + 1 <= n; i++) dp[2][i] = 0; for (int len = 3; len <= n; len++) { for (int i = 1; i+len-1<=n; i++) { int j = i+len-1; dp[i][j] = INF; for (int k = i+1; k <= j-1; k++) { dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]); } } } printf("%d\n", dp[1][n]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。