SPOJ - LSORT

Problem Statement:
SPOJ - LSORT

Summary:
Sort a permutation of [1..N] by the following rule:
1. Start with P the permutation of [1..N], and Q an empty set [].
2. For each step i, we can choose any element in P and append it to beginning or end of Q. We incur cost i*x, where x is the position of the element in P at that time.
3. In the end Q must be in sorted ascending order.

Find the minimal cost possible to perform this operation.



Solution:
A nice problem! Before doing the usual DP on the string, we need to precompute the positions of elements in P after removing several elements to Q, and there is a nice pattern that makes this computation possible and very efficient. Let's say Q has endings i and j. Notice that elements from i to j are already in sorted order. We can either take i-1 or j+1 from P, and for each we can calculate its current position by observing that it is equal to the number of elements in i to j that are place behind i-1 or j+1 in the original array P. After computing the positions of all elements given i or j, we can do a simple DP: minimal cost to build Q[i..j] is the minimum between cost to build Q[i..j-1] + cost of placing j, or cost to build Q[i+1..j] + cost of placing i.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/*
A[i] are elements.
P[i] is the position of i in A[i].
X[i][k] = the value x (position of element i from the left) after we
used items [i+1 .. k] where we want to place i to the left.
Y[i][k] = the value x after we used items [k .. i-1] where we want 
to place i to the right.
X[i][k] = X[i][k-1] - (P[k] < P[i] ? 1 : 0);
Y[i][k] = Y[i][k+1] - (P[k] < P[i] ? 1 : 0);
*/

int A[1003];
int P[1003];
int X[1003][1003], Y[1003][1003];
int dp[1003][1003];
int N;
int INF = (int) 1e9;
void solve(){
    for(int i=0;i<N;++i){
        P[A[i]-1] = i;
    }
    for(int i=0;i<N;++i){
        X[i][i] = P[i];
        for(int k=i+1;k<N;++k){
            X[i][k] = X[i][k-1] - (P[k] < P[i] ? 1 : 0);
        }
    }
    for(int i=0;i<N;++i){
        Y[i][i] = P[i];
        for(int k=i-1;k>=0;--k){
            Y[i][k] = Y[i][k+1] - (P[k] < P[i] ? 1 : 0);
        }
    }
    for(int i=0;i<N;++i){
        dp[i][i] = P[i]+1;
    }
    for(int k=1;k<N;++k){
        for(int i=0;i+k<N;++i){
            int j=i+k;
            int n=k+1;
            dp[i][j] = min(dp[i+1][j] + (X[i][j]+1)*n, dp[i][j-1] + (Y[j][i]+1)*n);
        }
    }
    printf("%d\n", dp[0][N-1]);
}

int main(){
    int tc;
    cin>>tc;
    while(tc--){
        scanf("%d", &N);
        for(int i=0;i<N;++i){
            scanf("%d", &A[i]);
        }
        solve();
    }
    return 0;
}