[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology