1302. Igiełka [ETI07F1]

[ronwsh]

Co dokładnie w tym zadaniu oznacza, że namiot jest naprawiony. Czy wystarczy zaszyć część "dziur", czy wszystkie? Jakoś nie mogę wybić się ponad 3 testy ;/.

[Artur_Laskowski]

Witam, mam następujący problem:
Rozwiązałem to zadanko, a przynajmniej tak mi się wydawało, niestety dostałem jedynie 8 pkt, czy mógłby mnie ktoś naprowadzić dlaczego coś jest źle?

// Programowanie Dynamiczne
#include <iostream>
#define MAX 100000000
using namespace std;
int Namioty[101][201];
int Zolta[101][201];
int Zgloszenia[101][2];
int Maximum(int a, int b)
{
    if(a>=b)    return a;
    else        return b;
}
int Minimum(int a,int b)
{
    if(a<=b)    return a;
    else        return b;
}
int main()
{
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 201; j++)
            Namioty[i][j] = Zolta[i][j] = 0;
    int Ile_zg,MaxZiel,MaxZol;
cin >> Ile_zg >> MaxZiel >> MaxZol;
int zol,ziel;
for(int i = 1; i <= Ile_zg; i++)
{
    cin >> ziel >> zol;
    Zgloszenia[i][0] = ziel;
    Zgloszenia[i][1] = zol;
}

for(int i = 1; i <= Ile_zg; i++)
        for(int j = 1; j <= MaxZiel; j++)
            {
                if(Zgloszenia[i][0] <= j)
                {
                Namioty[i][j] = Maximum(Namioty[i-1][j],Namioty[i-1][j-Zgloszenia[i][0]]+1);
                }
                else
                {
                    Namioty[i][j] = Namioty[i-1][j];
                }
            }

for(int i = 1; i <= Ile_zg; i++)
    for(int j = 1; j <= MaxZiel; j++)
        {
            if(Namioty[i][j] > Namioty[i-1][j])
            {
                Zolta[i][j] = Zolta[i-1][j-Zgloszenia[i][0]]+Zgloszenia[i][1];
            }
            else
            {
                Zolta[i][j] = Minimum(Zolta[i-1][j],Zolta[i-1][j-Zgloszenia[i][0]]+Zgloszenia[i][1]);
            }
        }


for(int i = 1; i <= Ile_zg; i++)
    for(int j = 1; j <= MaxZiel; j++)
        {
            if(Zolta[i][j] > MaxZol)    Namioty[i][j] = 0;
        }
int Max = 0;
for(int i = 1; i <= Ile_zg;i++)
    for(int j = 1; j <= MaxZiel; j++)
        if(Namioty[i][j] > Max ) Max = Namioty[i][j];

cout << Max << endl;
}

-- Śr gru 26, 2012 11:16 pm --

Naprawdę nikt nie ma pomysłu ?

[gabbek]

Wydaje mi się, że moja trójwymiarowa tablica jest za duża dla wartości graniczynych, zastanawiałem się jak to zrobić troszkę inaczej, ale narazie bez pozytywnych skutków
Dziekuję ślicznie za edycję mojego poprzedniego postu! Już usuwam również poprzedni kod.

[michalkol3]

Czy w zadaniu igiełka w przykładzie pierwszym wyjście nie powinno być 4? Wydaje mi się że dla obu zasobów nici będzie można zszyć 4 namioty.

[narbej]

Wydaje mi się

Tak.

[michalkol3]

Dzięki narbej