Poj Solution 3042

```http://poj.org/problem?id=3042

#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;

int x[1001];
__int64 ans[1001][1001][2];

int main() {
int i, j, n, k;
scanf( "%d%d", &n, &k );

for( i=0; i<n; i++ ) {
scanf( "%d", &x[i] );
}

x[n] = k;

std::sort( x, x+n+1 );
for( i=0; i<=n; i++ )
if( x[i] == k ) {
k = i;
break;
}

memset( ans, 0x7f, sizeof ans );
ans[k][k][0] = ans[k][k][1] = 0;

for( i=k; i>=0; i-- )
for( j=k; j<=n; j++ ) {
if( i ) {
if( ans[i-1][j][0] > ans[i][j][0] + (x[i]-x[i-1])*(i+n-j) )
ans[i-1][j][0] = ans[i][j][0] + (x[i]-x[i-1])*(i+n-j);
if(ans[i-1][j][0] > ans[i][j][1] + (x[j]-x[i-1])*(i+n-j) )
ans[i-1][j][0] = ans[i][j][1] + (x[j]-x[i-1])*(i+n-j);
}
if( j < n ) {
if( ans[i][j+1][1] > ans[i][j][0] + (x[j+1]-x[i])*(i+n-j) )
ans[i][j+1][1] = ans[i][j][0] + (x[j+1]-x[i])*(i+n-j);
if( ans[i][j+1][1] > ans[i][j][1] + (x[j+1]-x[j])*(i+n-j) )
ans[i][j+1][1] = ans[i][j][1] + (x[j+1]-x[j])*(i+n-j);
}
}

k = ans[0][n][0];
if( k > ans[0][n][1] )
k = ans[0][n][1];
printf( "%dn", k );

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.