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; } };