LA 6892 The Safe Secret（矩阵连乘）

https://vjudge.net/problem/UVALive-6892

题意：

给出n个数字和n个符号（+，-，*和？），？可以为+，-，*中任意一个，现在要计算出这个式子的最小值和最大值，并且运算顺序随意，也就是可以随便加括号。之后进行旋转之后继续计算。比如一开始给的是1 ? 5 + 0 ? -2 - -3 *，那么旋转之后就是上面的第二行了，这样一共需要旋转n次，也就是说要计算n次。

思路：
运算顺序随意，有没有感觉很像矩阵连乘？

这道题目就是升级版的矩阵连乘吧。

因为是可以旋转的，那么就在后面再加一行变成线性。

之后就和矩阵连乘的做法差不多了，用两个数组来保存，一个保存最大值，另一个最小值即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long ll;

 typedef pair<int,long long> pll;

 const ll INF = 1LL<<;

 const int maxn=+;

 int n;

 ll f[maxn][maxn];

 ll g[maxn][maxn];

 char op[maxn];

 int main()

 {

     //freopen("input.txt","r",stdin);

     while(~scanf("%d",&n))

     {

         for(int i=;i<=*n;i++)

         for(int j=;j<=*n;j++)

         {

             f[i][j]=-INF;

             g[i][j]=INF;

         }

         for(int i=;i<=n;i++)

         {

             scanf("%lld %c",&f[i][i],&op[i]);

             f[n+i][n+i]=f[i][i];

             g[i][i]=g[n+i][n+i]=f[i][i];

             op[n+i]=op[i];

         }

         for(int r=;r<=n;r++)

         {

             for(int i=;i<=*n-r+;i++)

             {

                 int j=i+r-;

                 for(int k=i;k<j;k++)

                 {

                     if(op[k]=='+'||op[k]=='?')

                     {

                         f[i][j]=max(f[i][j],f[i][k]+f[k+][j]);

                         g[i][j]=min(g[i][j],g[i][k]+g[k+][j]);

                     }

                     if(op[k]=='-'||op[k]=='?')

                     {

                         f[i][j]=max(f[i][j],f[i][k]-g[k+][j]);

                         g[i][j]=min(g[i][j],g[i][k]-f[k+][j]);

                     }

                     if(op[k]=='*'||op[k]=='?')

                     {

                         f[i][j]=max(f[i][j],f[i][k]*f[k+][j]);

                         f[i][j]=max(f[i][j],g[i][k]*g[k+][j]);

                         f[i][j]=max(f[i][j],f[i][k]*g[k+][j]);

                         f[i][j]=max(f[i][j],g[i][k]*f[k+][j]);

                         g[i][j]=min(g[i][j],f[i][k]*f[k+][j]);

                         g[i][j]=min(g[i][j],g[i][k]*g[k+][j]);

                         g[i][j]=min(g[i][j],f[i][k]*g[k+][j]);

                         g[i][j]=min(g[i][j],g[i][k]*f[k+][j]);

                     }

                 }

             }

         }

         for(int i=;i<=n;i++)

         {

             printf("%lld%lld",abs(g[i][i+n-]),abs(f[i][i+n-]));

         }

         printf("\n");

     }

     return ;

 }