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