题目链接：https://nanti.jisuanke.com/t/31711
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn =1e3+5;
const int mod=1e9+7;
ll dat[maxn];
char op[10];
/*
题目大意：题目没怎么仔细看。。。
看样例我大概能感觉到，
m种符号必须选，然后n个数字可以有选择性的选，
并且要按序，求最优值。一个较为经典的DP问题，
如果要求出最大解，维护最大值是不能得到的，
因为有负数的参与，所以我们维护最大值和最小值。
首先分析区间性质，假设到了i,j二维点，
i,j二维点的最大值最小值如何产生呢，
不管那么多，反正答案肯定是由极值产生的，
所以我们dp数组维护的就是极值，
所以用维护好的两个极值去产生运算，最后在二维点取最大最小即可维护起来。
我有个WA点，，，，选择区间记得还有不选的选项，我WA了四次。。。就因为那一行。。。PS:不想初始化DP数组的朋友要手动精确的推答案产生的区间，就是定义域啦。T_T
*/ll dp1[10][maxn],dp2[10][maxn];///维护一个最大值的DP,一个最小值的DP
ll cpt(ll x,ll y,char p)
{if(p=='+') return 1LL*(x+y);if(p=='-') return 1LL*(x-y);if(p=='*') return 1LL*(x*y);if(p=='/') return 1LL*(x/y);
}
int n,m,q;
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&q);for(int i=0;i<n;i++) scanf("%lld",&dat[i]);scanf("%s",op);dp1[0][0]=dp2[0][0]=cpt(q,dat[0],op[0]);for(int i=1;i<n-m+1;i++){dp1[0][i]=max(dp1[0][i-1],cpt(q,dat[i],op[0]));dp2[0][i]=min(dp2[0][i-1], cpt(q,dat[i],op[0]));}for(int i=1;i<m;i++){dp1[i][i]=cpt(dp1[i-1][i-1],dat[i],op[i]);dp2[i][i]=cpt(dp2[i-1][i-1],dat[i],op[i]);for(int j=i+1;j<n-m+i+1;j++){dp1[i][j]=dp1[i][j-1],dp2[i][j]=dp2[i][j-1];///这一行必须有,维护一个不做选择的解ll tp1=cpt(dp1[i-1][j-1],dat[j],op[i]);ll tp2=cpt(dp2[i-1][j-1],dat[j],op[i]);dp1[i][j]=max(dp1[i][j],max(tp1,tp2));dp2[i][j]=min(dp2[i][j],min(tp1,tp2));}}printf("%lld\n",dp1[m-1][n-1]);}return 0;
}