백준 1823번, 수확 풀이

문제

백준 1823번

풀이

$ dp[i][j] = $ 왼쪽에서 $ i $번째, 오른쪽에서 $ j $번째를 뽑을 차례일 때의 최대 이익으로 점화식을 세우면 풀 수 있습니다. (단, $i < j$)

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

int dp[2001][2001];
int vec[2001];

int solve(int l, int r, int c) {
	int &ret = dp[l][r];
	if (ret) return ret;
	if (l > r) return 0;
	return ret =
			       max(
					       solve(l + 1, r, c + 1) + c * vec[l],
					       solve(l, r - 1, c + 1) + c * vec[r]
			       );
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> vec[i];
	cout << solve(1, n, 1);
}