题意：给你n个矩阵，让你连乘，怎么样处理先乘哪两个后乘哪两个 会导致计算次数最少，简单线性数学知识：矩阵乘法的 运算次数是跟乘的顺序有关的，并且输出来
这个数据输出是比较繁琐的，还好前面做过几道 都是类似于记录路径 并输出的，所以很熟练的用递归解决了
这是一道矩阵连乘问题，区间DP，典型的经典例子
#include #include #include #include #include #include #include #include #include #include #include #include #include //#define ll long long #define ll __int64 #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen(c:\Users\linzuojun\desktop\input.txt, r, stdin) //#define OUT freopen(c:\Users\linzuojun\desktop\output.txt, w, stdout) int dp[10 + 5][10 + 5]; int path[10 + 5][10 + 5]; typedef struct Node { int r,c; int id; }; Node node[1000 + 5]; void Printf(int x,int y) { if(x == y) { cout< >n,n) { clear(); for(int i=0;i >node[i].r>>node[i].c; node[i].id = i; } for(int i=0;i dp[i][k] + dp[k + 1][j] + node[i].r * node[k + 1].r *node[j].c) { dp[i][j] = dp[i][k] + dp[k + 1][j] +node[i].r * node[k + 1 ].r * node[j].c; path[i][j] = k; } } } } cout<