[TIOJ] 1145. 6.糊塗情報員

題目連結:http://tioj.infor.org/problems/1145

---

原本看第一眼覺得跟經典的矩陣安排一樣，結果寫下去才發現比矩陣安排麻煩，因為他不只一種計算方法，所以如果單純算最大值的話，會不符合最佳子結構而不能DP(例如你可能減一個負數反而會變大，但是負數並不是最佳的)。所以我同時存了最大及最小值，這時加法時的最大值必定是兩個最大值相加，同理最小值；減法的話則反過來就好了，然而乘法的話有可能是負的乘負的，正的乘負的...比較複雜，所以我就直接讓他是所有情況取min跟max了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second

const int N = 50 + 5;
const lld INF = 1LL<<40;

char str[1000];
vector<int> nums;
vector<char> opt;
PLL dp[N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>str;
	nums.PB(0);
	for(int i=0;str[i]!='\0';i++){
		if('0'<=str[i] and str[i]<='9'){
			nums.back() = nums.back()*10+str[i]-'0';
		}else{
			opt.PB(str[i]);
			nums.PB(0);
		}
	}
	int cnt=nums.size();
	fill(dp[0], dp[cnt]+cnt, (PLL){0, INF});
	for(int i=0;i<cnt;++i)
		dp[i][i]={nums[i], nums[i]};
	for(int j=0;j<cnt;j++){
		for(int i=j;i>=0;i--){
			for(int k=i;k<j;k++){
				if(opt[k]=='+'){
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].FF+dp[k+1][j].FF);
					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].SS+dp[k+1][j].SS);
				}else if(opt[k]=='-'){
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].FF-dp[k+1][j].SS);
					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].SS-dp[k+1][j].FF);
				}else if(opt[k]=='*'){
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].FF*dp[k+1][j].FF);
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].FF*dp[k+1][j].SS);
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].SS*dp[k+1][j].FF);
					dp[i][j].FF = max(dp[i][j].FF, dp[i][k].SS*dp[k+1][j].SS);

					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].FF*dp[k+1][j].FF);
					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].FF*dp[k+1][j].SS);
					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].SS*dp[k+1][j].FF);
					dp[i][j].SS = min(dp[i][j].SS, dp[i][k].SS*dp[k+1][j].SS);
				}
			}
		}
	}
	cout<<dp[0][cnt-1].FF<<'\n';
	return 0;
}