ferinの競プロ帳

競プロについてのメモ

SRM624 div1easy BuildingHeights

考えたこ

題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。
dp[i][j] = (i+2個同じ高さのビルをつくる際にheights[j]の高さに合わせるときのコスト)をO(N^2)で計算できれば解けそう。i=0のときは階差数列を求めれば良い。DPテーブルを書いていると累積和っぽくやればできそうなことに気づく。i=0以外のときはdp[i][j] = dp[i-1][j] + (heights[j+i+1] - heights[j])でdpの更新を行えるのでO(N^2)でできる。
あとは各iについて最も小さいdp[i][j]の値を求めそのxorを出力すれば良い。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[4010][4010];
class BuildingHeights {
  public:
  int minimum(vector <int> heights)
  {
    int n = heights.size();
    sort(ALL(heights));

    int ret = 0;
    REP(i, n-1) {
      int mi = INF;
      REP(j, n-i-1) {
        dp[i][j] = heights[j+i+1] - heights[j];
        if(i > 0) dp[i][j] += dp[i-1][j+1];
        chmin(mi, dp[i][j]);
      }
      ret ^= mi;
    }

    return ret;
  }
};