Poj Solution 3184

http://poj.org/problem?id=3184

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

int l[10000];
int temp[2][10001], *ans1 = temp[0], *ans2 = temp[1];

int main( ) {
    int n, len, i, j, d1, d2, rest, t, k, *ans_i_j, *ans_i1_j;

    scanf( "%d%d", &n, &len );

    for( i=0; i<n; i++ )
        scanf( "%d", l+i );

    d1 = len/(n-1);
    d2 = d1 + (len%(n-1)?1:0);
    rest = len - d1*(n-1);

    ans1[0] = l[0]+1;

    for( i=0; i<n-1; i++ ) {
        
        j = 0;

        if( n-1-i<rest )
            j = rest-(n-1-i);

        ans_i_j = &ans1[j];
        ans_i1_j = &ans2[j];
        k = (i-j)*d1+j*d2-l[i+1];
        *ans_i1_j = 0;

        for( ; j<=i && j<=rest; j++ ) {
            if( *ans_i_j ) {
                t = *ans_i_j + abs( k+d1 );

                if( !*ans_i1_j || *ans_i1_j > t )
                    *ans_i1_j = t;

                ans_i1_j++;
                if( j < rest ) {
                    *ans_i1_j = *ans_i_j + abs( k+d2 );
                }
            }
            else {
                ans_i1_j++;
                *ans_i1_j = 0;
            }

            ans_i_j++;
            k += d2-d1;
        }
        swap( ans1, ans2 );
    }

    printf( "%dn", ans1[rest]-1 );
    return 0;
}





											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *