Poj Solution 1829

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
int ans[1025][161], s[1025];
int v[161], n, m;
const int MAX = ( (unsigned int)1<<31-1 );
void clac( ) {
    int i, j, k, t, h, best;    
    memset( ans, 0x7F, sizeof ans );    
    ans[1][1] = v[1];
    s[1] = v[1];
    for( i=2; i<=n; i++ ) {
        for( j=2; j<=i&&j<=m; j++ ) {
            best = ans[i-1][j-1]+v[j];
            h = i/j;
            if( h > i-j+1 )
                h = i-j+1;
            for( k=2; k<=h; k++ )
                if( ( t = ans[i-k][j-1] + s[k] + v[j]*k*k ) < best )
                    best = t;
            ans[i][j] = best;
        }
        best = MAX;
        for( j=2; j<=i&&j<=n; j++ )
            if( ans[i][j] < best )
                best = ans[i][j];
        s[i] = best;
        ans[i][1] = s[i] + v[1]*i*i;
    }

}
int main( ){
    int t, i;
    scanf( "%d", &t );
    while( t-- ) {
        scanf( "%d %d", &n, &m );
        for( i=1; i<=m; i++ )
            scanf( "%d", &v[i] );
        std::sort( v+1, v+m+1 );
        clac( );
        printf( "%dn", s[n] );
    }
    return 0;
}