ACM-ICPC 2018 焦作赛区网络预赛 B Mathematical Curse(DP)
https://nanti.jisuanke.com/t/31711
题意
m个符号必须按顺序全用，n个房间需顺序选择，有个初始值，问最后得到的值最大是多少。
分析
如果要求出最大解，维护最大值是不能得到的，因为有负数的参与，所以我们维护最大值和最小值。不管那么多，反正答案肯定是由极值产生的。
定义dp1[i][j]为用了i个符号，走了j间房后的最大值。因而dp2[][]就是对应的最小值。然后按要求转移。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; ll dp1[6][1010],dp2[6][1010]; int a[1010]; char f[1010]; int main(){ int n,m,k; int t; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%s",f+1); //puts(f+1); memset(dp1,-inf,sizeof(dp1)); memset(dp2,inf,sizeof(dp2)); for(int j=0;j<=n;j++) dp1[0][j]=dp2[0][j]=k; for(int i=1;i<=m;i++){ for(int j=i;j<=n;j++){ dp1[i][j]=dp1[i][j-1]; dp2[i][j]=dp2[i][j-1]; if(f[i]=='+'){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+a[j]); dp2[i][j]=min(dp2[i][j],dp2[i-1][j-1]+a[j]); }else if(f[i]=='-'){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]-a[j]); dp2[i][j]=min(dp2[i][j],dp2[i-1][j-1]-a[j]); }else if(f[i]=='*'){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]*a[j]); dp1[i][j]=max(dp1[i][j],dp2[i-1][j-1]*a[j]); dp2[i][j]=min(dp2[i][j],dp2[i-1][j-1]*a[j]); dp2[i][j]=min(dp2[i][j],dp1[i-1][j-1]*a[j]); }else{ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]/a[j]); dp1[i][j]=max(dp1[i][j],dp2[i-1][j-1]/a[j]); dp2[i][j]=min(dp2[i][j],dp2[i-1][j-1]/a[j]); dp2[i][j]=min(dp2[i][j],dp1[i-1][j-1]/a[j]); } } } printf("%lld ",dp1[m][n]); } return 0; }