首页 > 代码库 > hlg1600线性代数中的矩阵问题【区间dp】
hlg1600线性代数中的矩阵问题【区间dp】
大意：
告诉你n个矩阵的行数和列数
比如说
3
2 3 4 5
代表有3个矩阵第一个矩阵2 * 3 第二个矩阵 3 * 4 第三个矩阵4 * 5
并且知道只有连续的矩阵才可以相乘
问最后相乘的次数最少是多少
分析：
用区间dp可以做
每次递归调用的时候枚举每个分割点
最后加上附带的价值即可
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 105; 7 const int INF = 1000000000; 8 9 int dp[maxn][maxn];10 int a[maxn];11 12 int ddp(int i, int j) {13 if(dp[i][j] != -1) return dp[i][j];14 if(i + 1 == j) {15 return dp[i][j] = 0;16 }17 int Min = INF;18 for(int k = i + 1; k < j; k++) {19 Min = min(Min , ddp(i, k) + ddp(k, j) + a[i] * a[k] * a[j]);20 }21 return dp[i][j] = Min;22 }23 24 int main() {25 int t;26 int n;27 scanf("%d",&t);28 while(t--) {29 scanf("%d",&n);30 for(int i = 1; i <= n + 1; i++) {31 scanf("%d",&a[i]);32 }33 if(n == 1) {34 puts("0");35 continue;36 }37 memset(dp, -1, sizeof(dp));38 printf("%d\n", ddp(1, n + 1));39 // for(int i = 1; i <= n + 1; i++) {40 // for(int j =1; j <= n + 1; j++) {41 // printf("%d %d %d\n", i, j, dp[i][j]);42 // }43 44 }45 return 0;46 }
hlg1600线性代数中的矩阵问题【区间dp】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。