[サムスン148888]挿入演算子

https://www.acmicpc.net/problem/14888

問題の説明

N個のシーケンス

N-1個の演算子をN個のシーケンスの間に挿入すると、計算結果の最高値と最高値が検索され、

演算子は、+、-、*、/の順にいくつか与えられます.

計算は優先順位がなく、前から順に行います.

負数/正数を計算すると、円分を求めて負数化します.(除算された数は常に正の値です.)

アイデア

N<11であるため完全に探索可能と考えられ,これまで計算した値を再帰関数で受け取り,4つの演算子を加えて1回再帰すればよい.
参考までに結果(中間結果を含む)は10万(10^9)でintで解決できます.

すくい取る

が実現するのに時間がかかります^^...最初は、4つの演算子のFOR文を一般的なオーバーラッププロシージャに変換します(中間プロシージャは少し異なります).
それが気に入らなかったのでforを外して1行だけ書いて戻ってきました^^..

除算実装では,負数/正数,正数/正数ボックスを逆算してどこが間違っているのかわからないので,trakerランベクトルに生成結果の演算子順序を格納し,結果が出たときに撮った.

コード#コード#

https://www.acmicpc.net/source/23167877

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int> nums;
int mmin=pow(10,9), mmax=-pow(10,9);//전체 결과중에서
int counter = 0;
void one_proc(int mom_res, int s, vector<int> yeons,vector<int> tracker) {//s는 연산자가 적용될 인덱스
	counter++;

	if (s == nums.size()) {
		/*
		cout << "계산결과 비교중" << mmin << " , " << mmax << " , " << mom_res << endl;
		for (int i = 0; i < tracker.size(); i++) {
			cout << tracker[i] << " ";
		}
		cout << endl;
		*/
		mmin = min(mmin, mom_res);
		mmax = max(mmax, mom_res);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int res = mom_res;
		if (yeons[i] <= 0) {
			continue;
		}
		yeons[i]--;
		
		if (i == 0) {
			res = res + nums[s];
		}
		else if (i == 1) {
			res = res - nums[s];
		}
		else if (i == 2) {
			res = res * nums[s];
		}
		else if (i == 3) {
			if (res > 0) {
				res = res / nums[s];
			}
			else {
				res = -(abs(res) / nums[s]);
			}
		}
		vector<int> temp_tracker = tracker;
		temp_tracker.push_back(i);
		/*
		cout << "right before dfs" << endl;
		for (int i = 0; i < temp_tracker.size(); i++) {
			cout << temp_tracker[i] << " ";
		}
		cout << " == " << res << endl;
		*/
		one_proc(res, s + 1, yeons,temp_tracker);
		yeons[i]++;//복구
	}
}


int main() {
	int n;
	vector<int> yeons;//4가지 연산자의 개수

	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		nums.push_back(num);
	}
	for (int i = 0; i < 4; i++) {
		cin >> num;
		yeons.push_back(num);
	}
	vector<int> tracker;
	one_proc(nums[0], 1, yeons,tracker);
	cout << mmax << endl;
	cout << mmin << endl;
}