Poj Solution 1946

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

#include <iostream>
using namespace std;
int maxs[101][101], n, e, d;
//       ʱ�� ��
int need[101][101];
//         ·�� ��
void init()
{
    int t, s, v, h;
    cin>>n>>e>>d;

    for( t=0; t<=d; t++ )
        maxs[t][0] = 0;
    for( h=0; h<=e; h++ )
        maxs[0][h] = 0;
    for( t=1; t<=d; t++ )
    for( h=1,v=0,s=0; h<=e; h++ )
    {
        while( (v+1)*(v+1)*t <= h )
            v++;
        maxs[t][h] = v*t + (h-v*v*t)/(2*v+1);
    }
    for( h=0; h<=e; h++ )
    {
        t = 0;
        for( s=0; s<=d; s++ )
        {
            while( t<=d && maxs[t][h] < s )
                t++;
            if( t > d ) need[s][h] = -1;
            else need[s][h] = t;
        }
    }

}
int tm[21][101];
//     ��  ·��
int main()
{
    int i, j, k;
    init();
    for( i=0; i<=n; i++ )
    for( j=0; j<=d; j++ )
        tm[i][j] = -1;    
    tm[0][0] = 0;
    for( i=1; i<=n; i++ )
    for( j=0; j<=d; j++ )
    {
        tm[i][j] = tm[i-1][j];
        for( k=0; k<j; k++ )
            if( tm[i-1][k] >=0 && need[j-k][e-k] >=0 && ( tm[i][j]<0 || tm[i-1][k] + need[j-k][e-k] < tm[i][j] ) )
                tm[i][j] = tm[i-1][k] + need[j-k][e-k];
    }

    if( tm[n][d] < 0 ) tm[n][d] = 0;    
    cout<<tm[n][d]<<endl;
    return 0;
}