# Poj Solution 1946

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

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

for( t=0; t<=d; t++ )
maxs[t] = 0;
for( h=0; h<=e; h++ )
maxs[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;
//     ��  ·��
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;
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;
}
```
This entry was posted in poj. Bookmark the permalink.