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 }

?

轉載于:https://www.cnblogs.com/zyb993963526/p/6955199.html

總結

以上是生活随笔為你收集整理的LA 6892 The Safe Secret（矩阵连乘）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。