1839D - Ball Sorting - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 88
#define dout if (0) cout
#endif
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (int i=0;i<a.size();i++) cin>>a[i]; return cin; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define RE(i, n) for (int i = 0; i < n; i++)
#define RE2(i, start, n) for (int i = start; i < n; i++)

#define MULTI_CASES
#define LOCAL_MULTI_CASES

void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 2);
  RE2(i, 1, n + 1) {
    cin >> a[i];
  }
  a[0] = 0; a[n + 1] = n + 1;
  
  vector<vector<int>> dp(n + 2, vector<int>(n + 1, 0));
  
  // dp[0][k] = 0;
  // dp[i][0]????
  for (int i = 1; i <= n + 1; i++) {
    dp[i][0] = (a[i] > a[i - 1]) ? dp[i - 1][0] : INT_MAX;
    
    for (int k = 1; k <= n; k++) {
      dp[i][k] = INT_MAX;
      
      if (a[i] > a[i - 1]) {
        dp[i][k] = min(dp[i][k], dp[i - 1][k]);
      }
      
      for (int j = 0; j + 1 <= i - 1; j++) {
        if (a[i] < a[j]) continue;
        if (dp[j][k - 1] == INT_MAX) continue;
        dp[i][k] = min(dp[i][k], dp[j][k - 1] + i - 1 - j);
      }
    }
  }
  
  RE2(k, 1, n + 1) {
    cout << dp[n + 1][k] << " ";  
  }
  cout << endl;
  
  
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int cases = 1;
  #if defined MULTI_CASES || (defined LOCAL && defined LOCAL_MULTI_CASES)
  cin >> cases;
  #endif
  for (int i = 0; i < cases; i++) {
    dout << "cases: " << i + 1 << endl;
    solve();
    dout << endl;
  }
  
  return 0;
}