#10468 숫자뽑기게임

www.acmicpc.net/problem/10468

10468번: 숫자뽑기게임

Ad-hoc한 구간 dp. 나중에 기억해 볼만해서 적어본다.

문제에서 주어진 연산의 특징은 마지막으로 선택하는 원소를 정해버리면, 구간이 2개로 분할되며 

추가 연산을 통해 값을 구해 낼 수 있다.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
using ll = long long;
ll n=1, A[210], dp[210][210];
ll find(ll l, ll r) {
	if (dp[l][r] != -1)return dp[l][r];
	if (l > r)return dp[l][r] = 0;
	ll ret = 0;
	for (int i = l+1; i <= r-1; i++)ret = max(ret, find(l, i) + find(i, r) + A[l] + A[i] + A[r]);
	return dp[l][r] = ret;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	while (n) {
		cin >> n;
		if (!n)return 0;
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i <= n; i++)cin >> A[i];
		cout << find(1, n) << '\n';
	}
}

dp[x][y]---> 구간 x부터 y까지 먹을때의 최솟값