[USACO] 백준 5945 - Treasure Chest

참고

이 문제는 "동적계획법으로 푸는 게임이론" 문제이다. 이 키워드에 대해 잘 모르고 있다면 2040 - 수 게임 문제에 대한 풀이를 보고 오는 것이 이해에 도움이 된다.

 

링크 - https://nicotina04.tistory.com/272

백준 2040 - 수 게임

풀이

두 명의 플레이어가 점수를 먹는 게임을 하므로 $max(First - Second)$를 구하는 문제가 된다.

 

게임 규칙은 단순하므로 $max(First - Second)$는 동적 계획법으로 어렵지 않게 계산할 수 있다.

 

하지만 문제에서 요구하는 것은 $max(First)$이다.

 

이때 $(First - Second) + sum = (First - Second) + (First + Second) = 2 First$이므로 $2 max(First)$가 답이 된다.

 

정답 코드 - C++

// #pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
// using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
int n;
int ar[5001];
int dp[5001][5001];
 
int memo(int l, int r)
{
  if (l > r) return 0;
  auto &ret = dp[l][r];
  if (ret != -1e9) return ret;
  int tmp = -1e9;
  tmp = max(tmp, ar[l] -memo(l + 1, r));
  tmp = max(tmp, ar[r] - memo(l, r - 1));
  return ret = tmp;
}
 
void solve()
{
  fill(&dp[0][0], &dp[0][0] + 5001 * 5001, -1e9);
  cin >> n;
  int pref = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i + 1];
    pref += ar[i + 1];
  }
  
  int val = memo(1, n);
  cout << (val + pref) / 2;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}