840 Cuburi3

[•TheNechiz]

Pentru

Cod:

20
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
1 20
2 19
3 18
4 17
5 16
6 15
7 14
8 13
9 12
19 11
20 10

R:

Cod:

11 74
20
10
9
8
7
6
5
4
3
2
1

?

[•SebiSebi]

Da. E corect.

[•TheNechiz]

Nu înțeleg.
Sortez cuburi după greutate și apoi determin cel mai lung subșir descrescător.
Iau 30p cu WA.

Cod:

10
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1

R:

Cod:

1 10
10

?

[•SebiSebi]

Principiul e corect. Incearca rezolvarea in O(N²), fara AIB sau AINT, care ia 100p. Succes!

[•TheNechiz]

Cel mai mare subșir descrescător cu programare dinamică.

Cod:

void Sdmax()
{
    int Max,t,k;
    ind=0;
    l[N] = 1;
    h=0;
    for( k = N - 1 ; k ; --k )
    {
        Max = 0;
        for( i = k+1 ; i <= N ; ++i )
            if( v[i].l>=v[k].l && Max < l[i] )
                Max = l[i];
        l[k] = Max + 1;
    }
    Max = l[1];
    t = 1;
    for( k = 1 ; k <= N ; ++k )
        if( Max < l[k] )
    {
        Max = l[k];
        t =k;
    }
    kMax = Max;
    rez[++ind] = v[t].p;
    h += v[t].l;
    for( i = t + 1; i <= N ; ++i )
        if( v[i].l >= v[t].l && l[i] == Max - 1 ){
            rez[++ind] = v[i].p;
            h += v[i].l;
            --Max;
        }
}

Sper că la asta te refereai.
Tot 30p.

[•PlayLikeNeverB4]

Cand faci dinamica, trebuie sa compari atat latura cat si greutatea.

[•SebiSebi]

El sorteaza crescator dupa greutate, deci nu mai e nevoie de a doua comparatie.  

L.E. Nu imi dau seama ce ar putea fi gresit. Daca nu reusesti sa revolvi pana la urma, da-mi un PM si iti dau sursa mea.

[•PlayLikeNeverB4]

Vezi ca tu trebuie sa cauti turnul cu suma laturilor maxima, nu cu numarul maxim de cuburi.

[•gapdan]

Imi poate sugera si mie cineva un test (altul fata de cele precizate la comentariile anterioare ) . Am facut problema dupa varianta 2 de la solutie, dar iau doar 30p..

Cod:

for (i=1;i<=n;++i)
    {
        int Max=0;
        for (j=1;j<i;++j)
            if (a[j].g>=a[i].g)
                if (best[j]>Max) {
                    Max=best[j];
                    poz[i]=j;
                    L[i]=L[j]+1;}
        best[i]=Max+a[i].l;
        if (best[i]>=sum) sum=best[i],p=i,lmax=L[i];;
    }
    printf("%d %d\n",lmax,sum);