首页 > 代码库 > LA 6892 The Safe Secret（矩阵连乘）
LA 6892 The Safe Secret（矩阵连乘）
https://vjudge.net/problem/UVALive-6892
题意：
给出n个数字和n个符号（+，-，*和？），？可以为+，-，*中任意一个，现在要计算出这个式子的最小值和最大值，并且运算顺序随意，也就是可以随便加括号。之后进行旋转之后继续计算。比如一开始给的是1 ? 5 + 0 ? -2 - -3 *，那么旋转之后就是上面的第二行了，这样一共需要旋转n次，也就是说要计算n次。
思路：
运算顺序随意，有没有感觉很像矩阵连乘？
这道题目就是升级版的矩阵连乘吧。
因为是可以旋转的，那么就在后面再加一行变成线性。
之后就和矩阵连乘的做法差不多了，用两个数组来保存，一个保存最大值，另一个最小值即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long ll;13 typedef pair<int,long long> pll;14 const ll INF = 1LL<<60;15 const int maxn=500+5;16 17 int n;18 ll f[maxn][maxn];19 ll g[maxn][maxn];20 char op[maxn];21 22 int main()23 {24 //freopen("input.txt","r",stdin);25 while(~scanf("%d",&n))26 {27 for(int i=1;i<=2*n;i++)28 for(int j=1;j<=2*n;j++)29 {30 f[i][j]=-INF;31 g[i][j]=INF;32 }33 34 for(int i=1;i<=n;i++)35 {36 scanf("%lld %c",&f[i][i],&op[i]);37 f[n+i][n+i]=f[i][i];38 g[i][i]=g[n+i][n+i]=f[i][i];39 op[n+i]=op[i];40 }41 42 for(int r=2;r<=n;r++)43 {44 for(int i=1;i<=2*n-r+1;i++)45 {46 int j=i+r-1;47 for(int k=i;k<j;k++)48 {49 if(op[k]==‘+‘||op[k]==‘?‘)50 {51 f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);52 g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);53 }54 55 if(op[k]==‘-‘||op[k]==‘?‘)56 {57 f[i][j]=max(f[i][j],f[i][k]-g[k+1][j]);58 g[i][j]=min(g[i][j],g[i][k]-f[k+1][j]);59 }60 61 if(op[k]==‘*‘||op[k]==‘?‘)62 {63 f[i][j]=max(f[i][j],f[i][k]*f[k+1][j]);64 f[i][j]=max(f[i][j],g[i][k]*g[k+1][j]);65 f[i][j]=max(f[i][j],f[i][k]*g[k+1][j]);66 f[i][j]=max(f[i][j],g[i][k]*f[k+1][j]);67 68 g[i][j]=min(g[i][j],f[i][k]*f[k+1][j]);69 g[i][j]=min(g[i][j],g[i][k]*g[k+1][j]);70 g[i][j]=min(g[i][j],f[i][k]*g[k+1][j]);71 g[i][j]=min(g[i][j],g[i][k]*f[k+1][j]);72 }73 }74 }75 }76 for(int i=1;i<=n;i++)77 {78 printf("%lld%lld",abs(g[i][i+n-1]),abs(f[i][i+n-1]));79 }80 printf("\n");81 }82 return 0;83 }
LA 6892 The Safe Secret（矩阵连乘）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。