AOJ 2431 House Moving - tubo28のブログ

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431

1 から ${ n }$ までの整数を並び替えた列 ${ x_1 , x_2, \cdots, x_n }$ が与えられる。 ${ x_i }$ をコスト ${ x_i }$ で好きな場所に移動できる。昇順にソートするのに必要なコストの最小値を求めよ。

解法

移動させるときはまとめて移動させればいいので、和が最大な増加部分列を求め、それをコストの総和 ${\frac{1}{2} n(n+1)}$ から引く。

${ dp(i) := i}$ 番目まででとれるコストの最大値

とし、普通の最長増加部分列問題のように ${ dp(i) = \max(\{ dp(j)+x_i | 1 \le j \le i-1 \}) }$ と更新していった。最大値を探すときに愚直にループを回すと ${O(n^{2})}$ になってしまうのでDP配列を Fenwick 木で持って ${O(n\log n)}$ まで高速化する。

和以外の演算の Fenwick 木を書いたのは初めてだった。

template <typename T>
struct fenwick_tree {
    vector<T> x;
    fenwick_tree(int n) : x(n, 0) { }
    T max(int j) {
        T S = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) S = std::max(x[j],S);
        return S;
    }
    void chmax(int k, T a) {
        for (; k < x.size(); k |= k+1) x[k] = std::max(x[k],a);
    }
};
 
int main(){
    ll n;scanf("%lld",&n);
    fenwick_tree<ll> dp(n+1);
    for(int i=0;i<n;i++){
        int x;scanf("%d",&x);
        dp.chmax(x,dp.max(x-1)+x);
        // for(int i=1;i<=n;i++){
        //     printf("%lld ",dp.max(i)-dp.max(i-1));
        // }
        // puts("");
    }
    printf("%lld\n",(ll)n*(n+1)/2 - dp.max(n));
}