BOJ 11066 파일합치기

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>

typedef long long int ll;
using namespace std;
#define INF 1234567890
#define N 200000

const int LIMIT = 1e+9;
int n, m;

int value[505];
pair<int, int> dp[505][505];

pair<int, int> solve(int left, int right) {
	/*if (left < 0 || right > n || left >= right) {
		return -1;
	}*/

	if (left == right) {
		return dp[left][right] = {
			0,
			value[left]
		};
	}

	/*if (right - left == 1) {
		return dp[left][right] = {
			value[left] + value[right],
			value[left] + value[right]
		};
	}*/

	pair<int, int>& res = dp[left][right];

	if (res.first != -1) {
		return res;
	}

	res.first = 0x7FFFFFFF;
	res.second = 0x7FFFFFFF;

	for (int i = left; i < right; i++) {
		pair<int, int> left_min = solve(left, i);
		pair<int, int> right_min = solve(i+1, right);

		int current_value = left_min.second + right_min.second;
		int total_cost = left_min.first + right_min.first + current_value;

		if (res.first > total_cost) {
			res.first = total_cost;
			res.second = current_value;
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int _T = 0;
	cin >> _T;
	while (_T--)
	{
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> value[i];
			memset(dp, 0xFF, sizeof(dp));
		}
		pair<int, int> res = solve(0, n - 1);
		cout << res.first << "\n";
	}

	return 0;
}