# PBinfo #4530 – flowers1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Vrei să-ți aranjezi vitrina florăriei în cel mai minunat mod cu putință. Ai F buchete de flori de diferite soiuri și cel puțin la fel de multe vaze aliniate pe un rând. Vazele sunt lipite de raft și sunt numerotate de la stânga la dreapta cu numere de la 1 la V, unde V este numărul de vaze. 

Buchetele pot fi mutate și sunt identificate în mod unic prin numere întregi între 1 și F. Aceste numere de identificare au o semnificație: ele determină ordinea necesară de apariție a buchetelor de flori în rândul de vaze, astfel încât buchetul i trebuie să fie într-o vază aflată șa stânga vazei care conține buchetul j ori de câte ori i < j. Să presupunem, de exemplu, că aveți un buchet de azalee (numerotat cu 1), un buchet de begonii (numerotat cu 2) și un buchet de garoafe (numerotat cu 3). Acum, toate buchetele trebuie puse în vaze păstrându-și numerele de identificare ordonate. Buchetul de azalee trebuie să fie într-o vază în stânga begoniilor, iar buchetul de begonii trebuie să fie într-o vază în stânga garoafelor. Dacă sunt mai multe vaze decât buchete de flori, atunci excesul va rămâne gol. O vază poate conține doar un buchet de flori. Fiecare vază are o caracteristică distinctă (la fel ca și florile). Prin urmare, punerea unui buchet de flori într-o vază are ca rezultat o anumită valoare estetică, exprimată printr-un număr întreg. Valorile estetice sunt prezentate într-un tabel, după cum se arată mai jos. O vază goală are o valoare estetică egală cu 0.

.tt td{vertical-align:middle !important; text-align:center;}



 Vaze 


 1  2  3  4  5 


 Buchete 
 1. Azalee 723-5-2416


 2. Begonii 521-41023


 3. Garoafe -215-4-2020




Conform tabelului, azaleele ar arăta grozav în vaza 2, dar ar arăta groaznic în vaza 4. 

Cerința
Pentru a obține cel mai plăcut efect trebuie să maximizezi suma valorilor estetice pentru aranjament, păstrând în același timp ordinea necesară a florilor. Dacă există mai multe aranjamente de valoare maximă totală, oricare dintre ele va fi acceptată. Trebuie să afișați exact un aranjament.

Date de intrare
Fișierul de intrare flowers.in conține pe prima linie numerele F V. Următoarele F linii conțin câte V numere întregi, astfel încât Aij este dat ca al j-lea număr de pe a (i+1)-a linie.

Date de ieșire
Fișierul de ieșire flowers.out va conține pe prima linie suma maximă a valorilor estetice pentru aranjament. A doua linie conține aranjamentul ca un șir de F numere astfel încât al k-lea număr din șir să identifice vaza în care este pus buchetul k.

Restricții și precizări

1 ≤ F ≤ 100, unde F este numărul de buchete de flori. Buchetele sunt numerotate de la 1 la F
F ≤ V ≤ 100 unde V este numărul de vaze
-50 ≤ Aij ≤ 50 unde Aij este valoarea estetică obținută punând buchetul de flori i în vaza j

Exemplu:
flowers.in

3 5 
7 23 -5 -24 16 
5 21 -4 10 23 
-21 5 -4 -20 20
flowers.out

53 
2 4 5

## Cod sursă C++

```cpp
/*
   Solves the problem using dynamic programming,
   time complexity: O ( item_nr * slot_nr )
*/
#include <fstream>
#define   MAX_SLOT_NR  	101
#define   MAX_ITEM_NR   101
using namespace std;
ifstream fin("flowers.in");
ofstream fout("flowers.out");
/* the table weight keeps the weight of each item in each slot  */
/* it will also be used to calculate the best (maximum) weights */
int    weight[MAX_ITEM_NR][MAX_SLOT_NR];
/* the table index will be used to keep the solution(s) */
int    f_index[MAX_ITEM_NR][MAX_SLOT_NR];
int    slot_nr;   /* the number of slots */
int    item_nr;   /* the number of items */
void get_input()
{
    int i,j;
    fin >> item_nr >> slot_nr;
    for (i=0; i < item_nr; i++)
        for (j=0; j < slot_nr; j++)
            fin >> weight[i][j];
}
void solve()
/* calculates the maximum sum of weights for each item in each slot */
/* and also fills the 'index' table with info about how we obtained */
/* this maximum (needed to output the solutions)                    */
{
    int i, j, k, wmax, imax;
    for (i=1; i < item_nr; i++)
    {
        imax = i-1;
        wmax = weight[i-1][imax];
        for (j=i; j <= (slot_nr - item_nr + i); j++)
        {
            if (weight[i-1][j-1] > wmax)
            {
                wmax = weight[i-1][j-1];
                imax = j-1;   /* record the index of maximum */
            }
            weight[i][j] += wmax;
            f_index[i][j] = imax;
        }
    }
}
void print_slots(int item, int slot)
/* postorder recursive function */
{
    int prev_slot;
    if (item == 0) fout << slot+1 << " ";
    else
    {
        prev_slot = f_index[item][slot];
        print_slots(item-1, prev_slot);
        fout << slot+1 << " ";
    }
}
void print_solution()
{
    int wmax;
    int imax;
    int j;
    /* take as max the first one */
    imax = item_nr - 1;
    wmax = weight[item_nr-1][imax];
    for (j=item_nr-1; j < slot_nr; j++)
        if ( weight[item_nr-1][j] > wmax )
        {
            wmax = weight[item_nr-1][j];
            imax = j;
        }
    fout << weight[item_nr-1][imax] << "\n";
    print_slots(item_nr-1, imax);
}
int main()
{
    get_input();
    solve();
    print_solution();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4530)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4530/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4530/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)