2018焦作网络赛Mathematical Curse

题意：开始有个数k,有个数组和几个运算符。遍历数组的过程中花费一个运算符和数组当前元素运算。运算符必须按顺序花费，并且最后要花费完。问得到最大结果。

用maxv[x][y]记录到第x个元素，用完了第y个运算符时的最大值，minv[x][y]为最小。那么maxv[x][y]要么第y个运算符在x-1之前就用过了，即max[x-1][y]，要么x-1之前用到了y-1，再在x的位置用运算符y;因此就是两者取大。还有如果当前遇到的是负数，那么要用最小的来乘，实际上是3者取大。

//#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include <stack>

#include <list>

using namespace std;

typedef long long lon;

lon maxv[][],minv[][],arr[];

const lon SZ=,INF=0x7FFFFFFFFFFFFFFF;

lon ope(lon a,lon b,char opr)

{

    if(opr=='+')return a+b;

    else if(opr=='-')return a-b;

    else if(opr=='*')return a*b;

    else return a/b;

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    lon casenum;

    cin>>casenum;

    for(lon time=;time<=casenum;++time)

    {

        lon n,m,k;

        cin>>n>>m>>k;

        for(lon i=;i<=n;++i)cin>>arr[i];

        string str;

        cin>>str;

        str=" "+str;

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

        {

            for(lon j=;j<=m;++j)

            {

                maxv[i][j]=-INF;

                minv[i][j]=INF;

            }

         }

        maxv[][]=minv[][]=ope(k,arr[],str[]);

        for(lon i=;i<=n;++i)maxv[i][]=minv[i][]=k;

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

        {

            for(lon j=;j<=m;++j)

            {

                if(j>i)break;

                else

                {

                    maxv[i][j]=max(maxv[i-][j],ope(maxv[i-][j-],arr[i],str[j]));

                    maxv[i][j]=max(maxv[i][j],ope(minv[i-][j-],arr[i],str[j]));

                    //if(i==2&&j==1)cout<<"m: "<<minv[i-1][j-1]<<" "<<arr[i]<<endl;

                    minv[i][j]=min(minv[i-][j],ope(maxv[i-][j-],arr[i],str[j]));

                    minv[i][j]=min(minv[i][j],ope(minv[i-][j-],arr[i],str[j]));

                }

            }

        }

//        for(lon i=1;i<=n;++i)

//        {

//            for(lon j=1;j<=m;++j)

//            {

//                cout<<maxv[i][j]<<" ";

//            }cout<<endl;

//        }

        lon resmax=-INF,resmin=INF;

        for(lon i=;i<=n;++i)resmax=max(resmax,maxv[i][m]);

        //for(lon i=1;i<=n;++i)resmin=max(resmin,maxv[i][m]);

        cout<<resmax<<endl;

    }

    return ;

}