Am atasat enuntul problemei, ma chinui de cateva zile la ea si tot nu stiu unde gresesc la rezolvare.
Algoritmul meu e simplu, am un vector was[ j ] <- semnifica ca suma a j de h'uri a fost atinsa si retin, in acelasi timp, si suma de n'uri. In Mt voi avea rezultatul final, iar in s tin minte suma tuturor n'urilor. La fiecare pas cand generez o suma noua Mt=min( Mt, s-was[ new_sum ] + new_sum^4 ); , nu inteleg unde as putea gresi, any ideas ?
#include <cstdlib>
#include <iostream>
#define Nmax 60
#define NNmax 600
#define oo 9999999999999999LL
/*
*
*/
using namespace std;
int was[NNmax];
bool wass[NNmax];
int nk[Nmax], hk[Nmax];
inline long long int solve( void )
{
int N, i;
long long int Mt=oo, j, p, maxim, s=0;
cin>>N;
for( i=1; i < N; ++i )
cin>>nk[i]>>hk[i], s+=nk[i];
wass[0]=true;
for( i=1, maxim=0; i < N; ++i )
{
for( j=maxim; j >= 0; --j )
if( wass[ j ] )
{
wass[ j+hk[i] ]=true;
was[ j+hk[i] ]=was[j]+nk[i];
p=j+hk[i];
Mt=min( Mt, s-was[ j+hk[i] ] + p*p*p*p );
maxim=min( 500LL, max( j+hk[i], maxim ) );
}
}
for( j=0; j <= maxim; ++j )
wass[j]=was[j]=false;
return Mt;
}
int main( void )
{
int T;
for( cin>>T; T; --T )
cout<<"Minimum fuel consumption = "<<solve()<<".\n";
return 0;
}