B. Mathematical Curse
题意就是给你一串运算符和一个初始值，你要按顺序使用这些运算符与一个序列中的数进行运算，序列中数的个数大于运算符的个数，要按先后顺序使用这些数而运算符，当然也可以选择不用某个数，但最后一定要把所有运算符用光。
我们用dp[i][j]表示到达第i个位置是使用j个运算符所能达到的最大值，然后就可以n*m进行转移，但是这道题过程中会出现负数，如果一个负数进行乘法，很明显我们应该用更小的负数去乘负数才能得到一个更大的数，所以我们只要开两个dp数组，一个保存最小值，一个保存最大值，乘法和除法的时候分别互相进行转移就可以了。
代码
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
#include<set>
#include<vector>
#include <time.h>
#include<string.h>
#define ll long long
using namespace std;
const int maxn = 1005;
const int Mod=1000000007;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll maxx[maxn][10];
ll minn[maxn][10];
int a[maxn];
char str[maxn];
int judge(char c)
{if(c=='+') return 1;else if(c=='-') return 2;else if(c=='*') return 3;else return 4;
}
void init(int n,int k)
{memset(maxx,-inf,sizeof(maxx));memset(minn,inf,sizeof(minn));for(int i=0;i<=n;i++){minn[i][0]=k;maxx[i][0]=k;}
}
int main()
{int t;scanf("%d",&t);while(t--){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);init(n,k);scanf("%s",str);for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){if(i>=j){maxx[i][j]=maxx[i-1][j];minn[i][j]=minn[i-1][j];}else{maxx[i][j]=-inf;minn[i][j]=inf;}}for(int j=1;j<=m;j++){if(i<j) continue;int ope=judge(str[j-1]);if(ope==1){maxx[i][j]=max(maxx[i][j],maxx[i-1][j-1]+a[i]);minn[i][j]=min(minn[i][j],minn[i-1][j-1]+a[i]);}if(ope==2){maxx[i][j]=max(maxx[i][j],maxx[i-1][j-1]-a[i]);minn[i][j]=min(minn[i][j],minn[i-1][j-1]-a[i]);}if(ope==3){maxx[i][j]=max(1LL*minn[i-1][j-1]*a[i],max(maxx[i][j],1LL*maxx[i-1][j-1]*a[i]));minn[i][j]=min(1LL*maxx[i-1][j-1]*a[i],min(minn[i][j],1LL*minn[i-1][j-1]*a[i]));}if(ope==4){maxx[i][j]=max(1LL*minn[i-1][j-1]/a[i],max(maxx[i][j],1LL*maxx[i-1][j-1]/a[i]));minn[i][j]=min(1LL*maxx[i-1][j-1]/a[i],min(minn[i][j],1LL*minn[i-1][j-1]/a[i]));}}}ll ans=-inf;for(int i=1;i<=n;i++){ans=max(ans,maxx[i][m]);}printf("%lld\n",ans);}return 0;
}