problema B

[•alexandru92]

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 ?

Cod:

#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;
}

[•popoiu.george]

Problema asta este si pe infoarena .

http://infoarena.ro/problema/calatorie

Se rezolva cu dinamica. Recurenta e ceva de genu :

M[ i ][ j ] = costul minim pentru a ajunge la planeta i folosind j unitati de superviteza.

Rezultatul il cauti pe ultima linie a matricii.

[•alexandru92]

Problema asta este si pe infoarena .

http://infoarena.ro/problema/calatorie

Se rezolva cu dinamica. Recurenta e ceva de genu :

M[ i ][ j ] = costul minim pentru a ajunge la planeta i folosind j unitati de superviteza.

Rezultatul il cauti pe ultima linie a matricii.

Aha, thanks