题意：有n个房间,m个诅咒，每个房间有一个数值，刚开始有一个初始值，每次进入一个房间可以选择消除诅咒或者不消除，消除诅咒只能顺序消除，消除诅咒就是拿初始值和房间的数值做运算，求最后最大的数是多少。
思路：因为运算是要按顺序的，那么规定dp1[i][j]为前i个数中运算了前j个运算符的最大值，因为数字有可能为负数，那么乘法和除法运算就要特殊处理了，因为乘上一个负数或者除一个负数的话，值越大结果就越小，所以还需要dp2[i][j]来表示前i个数运算了前j个运算符的最小值。
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #define ll long long const int max_=1005; using namespace std; ll dpmax[1005][10];//第-维是用到第几个数，第二维是用到第几个符号； ll dpmin[1005][10]; ll a[max_]; ll maxm,minm; char str[10]; int main() { int t; cin>>t; while(t--) { int n,m,c; cin>>n>>m>>c; memset(dpmax,0,sizeof(dpmax)); memset(dpmin,0,sizeof(dpmin)); for(int i=0;i<=n;i++) { dpmax[i][0]=c; dpmin[i][0]=c; } for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>str[i]; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(i>=j) { if(str[j]=='+') maxm=max(dpmax[i-1][j-1]+a[i],dpmin[i-1][j-1]+a[i]), minm=min(dpmax[i-1][j-1]+a[i],dpmin[i-1][j-1]+a[i]); if(str[j]=='-') maxm=max(dpmax[i-1][j-1]-a[i],dpmin[i-1][j-1]-a[i]), minm=min(dpmax[i-1][j-1]-a[i],dpmin[i-1][j-1]-a[i]); if(str[j]=='*') maxm=max(dpmax[i-1][j-1]*a[i],dpmin[i-1][j-1]*a[i]), minm=min(dpmax[i-1][j-1]*a[i],dpmin[i-1][j-1]*a[i]); if(str[j]=='/') maxm=max(dpmax[i-1][j-1]/a[i],dpmin[i-1][j-1]/a[i]), minm=min(dpmax[i-1][j-1]/a[i],dpmin[i-1][j-1]/a[i]); dpmax[i][j]=max(maxm,dpmax[i-1][j]); dpmin[i][j]=min(minm,dpmin[i-1][j]); } if(i==j) dpmax[i][j]=maxm, dpmin[i][j]=minm; } cout<<dpmax[n][m]<<endl; } }
参考博客：https://blog.csdn.net/baymax520/article/details/82719543
另外：
ios::sync_with_stdio(false);
输入加速器。
参考博客：https://blog.csdn.net/yujuan_mao/article/details/8119529