파일 합치기

Problem link: https://www.acmicpc.net/problem/11066

매우 간단한 DP 문제이나, 테스트케이스 수가 주어지지 않아 "이게 정말 TLE 안나고 풀릴까?"를 고민하게 만드는 문제이다.

간단한 DP로 풀어주면 TLE 안나고 정답이 나온다.

CACHE 정의는 아래와 같이 한다.

• CACHE[i][j]: 파일 i ~ j를 합칠 때 최소 비용

점화식은 아래와 같다.

• CACHE[i][j] = CACHE[i][m] + CACHE[m+1][j] + PSUM[j] - PSUM[i] + FILE[i] (i < j)
• CACHE[i][j] = 0 (i >= j)

#include <iostream>
#include <limits>
#include <algorithm>

using namespace std;

const int kMaxK = 500;

int K;
int FILES[kMaxK];
int PSUMS[kMaxK];
int CACHE[kMaxK][kMaxK];

int Solve(const int s, const int e)
{
  if (s >= e)
  {
    return 0;
  }

  int& ret = CACHE[s][e];

  if (ret != -1)
  {
    return ret;
  }

  ret = numeric_limits<int>::max();
  for (int m = s; m <= e; ++m)
  {
    ret = min(ret, Solve(s, m) + Solve(m + 1, e) + PSUMS[e] - PSUMS[s] + FILES[s]);
  }

  return ret;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Testcase
  int testcase;
  cin >> testcase;

  while (testcase--)
  {
    // Read Input
    cin >> K;
    for (int i = 0; i < K; ++i)
    {
      cin >> FILES[i];
    }

    // Initialize
    int psum = 0;
    for (int i = 0; i < kMaxK; ++i)
    {
      psum += FILES[i];
      PSUMS[i] = psum;
      for (int j = i; j < kMaxK; ++j)
      {
        CACHE[i][j] = -1;
      }
    }

    cout << Solve(0, K - 1) << '\n';
  }

  return 0;
}