题意：给你n个数，m个运算符，初始值为k

让你选择m个数进行计算，输出计算后的最大数，需要注意的是，计算选择必须按照顺序，不可乱序选择

本题是一个很显然的dp问题，枚举数和运算符进行计算即可。

需要注意的点1：因为计算中可能存在负数，所以我们需要同时维护一个最大值和最小值，当当前值为负数，且之后计算中存在负数时，我们就可以负负得正得到正数。

需要注意的点2：注意当我们枚举数和运算符时，当枚举的数的数量不大于运算符的数量

 

代码如下：

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1010, M = 10;
int n, m;
ll k;
ll a[N];
ll dpmax[N][M], dpmin[N][M];
char f[M];

int main()
{
	int T;
	scanf("%d", &T);
	
	while(T--){
		scanf("%d%d%lld", &n, &m, &k);
		
		for(int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		
		scanf("%s", f + 1);
		
		dpmax[0][0] = dpmin[0][0] = k;
		for(int i = 1; i <= n; i++){ 
			dpmax[i][0] = dpmin[i][0] = k;
			
			/*限制运算符的数量不得超过数的数量*/
			int jmax = min(m, i);
			for(int j = 1; j <= jmax; j++){
				dpmax[i][j] = dpmax[i - 1][j];
				dpmin[i][j] = dpmin[i - 1][j];
				
				ll tmax = dpmax[i - 1][j - 1];
				ll tmin = dpmin[i - 1][j - 1];
				
				switch(f[j]){
					case '+' : tmax += a[i]; tmin += a[i]; break;
					case '-' : tmax -= a[i]; tmin -= a[i]; break;
					case '*' : tmax *= a[i]; tmin *= a[i]; break;
					case '/' : tmax /= a[i]; tmin /= a[i]; break;	
				}
				if(tmax < tmin){
					ll temp = tmax;
					tmax = tmin;
					tmin = temp;
				}
				
				/*判断下临界问题，即当i==j的时候，必须选择是第i个数选择了第j个运算符进行计算*/
				if(i == j){
					dpmax[i][j] = tmax;
					dpmin[i][j] = tmin;
				}
				else{ 
					dpmax[i][j] = max(dpmax[i][j], tmax);
					dpmin[i][j] = min(dpmin[i][j], tmin);
				} 
			}
		}
		printf("%lld\n", dpmax[n][m]);
	}
	return 0;
}