区间DP-矩阵连乘问题

本文主要是介绍区间DP-矩阵连乘问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>/*=======================================
矩阵连乘问题
dp(i, j) = min( dp(i, k) + dp(k + 1, j) + S);
i < k < j;
dp(i, i) = 0;
========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 128;
//const int oo = 0x7fffffff;
const int oo = 0x3f3f3f3f;int dp[MAX_ITEM][MAX_ITEM];
int w[MAX_ITEM], pos[MAX_ITEM][MAX_ITEM];int DP(int l, int r)
{if(l == r)return 0;if(dp[l][r])return dp[l][r];int ans = oo, tmp = 0;for(int i = l; i < r; i++){tmp = DP(l, i) + DP(i + 1, r) + w[l - 1] * w[i] * w[r];if(ans > tmp){ans = tmp;pos[l][r] = i;}}return dp[l][r] = ans;
}void display(int l, int r)
{if(l == r){printf("A%d", l);return;}printf("(");display(l, pos[l][r]);display(pos[l][r] + 1, r);printf(")");
}int main()
{freopen("0-data.txt", "r", stdin);int n;while(scanf("%d", &n) != EOF){flush(dp, 0);flush(pos, 0);for(int i = 0; i <= n; i++)scanf("%d", w + i);printf("%d\n", DP(1, n));display(1, n);}return 0;
}

这篇关于区间DP-矩阵连乘问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---