首页 > 代码库 > 蓝桥杯：矩阵乘法（区间DP）
蓝桥杯：矩阵乘法（区间DP）
http://lx.lanqiao.cn/problem.page?gpid=T417
题意：……
思路：n=1000，一开始觉得区间DP会超时，后来想不到其他做法就这样做了，居然没超时。
状态转移：dp[l][r] = min(dp[l][r], dp[l][k] * dp[k][r] + num[l]*num[k]*num[r]).
表示用l*k的矩阵去和k*r的矩阵相乘，然后取最小。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 100000000000000000LL; 5 LL num[1010]; 6 LL dp[1010][1010]; 7 int main() { 8 LL ans = 0; 9 int n; cin >> n;10 for(int i = 0; i <= n; i++) scanf("%lld", &num[i]), dp[i][i] = num[i];11 for(int len = 2; len <= n; len++) {12 for(int l = 0; l + len <= n; l++) {13 int r = l + len;14 dp[l][r] = INF;15 for(int k = l + 1; k < r; k++) {16 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + num[l] * num[k] * num[r]);17 }18 }19 }20 cout << dp[0][n] << endl;21 return 0;22 }
蓝桥杯：矩阵乘法（区间DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。