Fűrészmalom
Feladat
A folyó mentén kitermelt fát N helyen gyűjtik össze és szállítják a folyón lefelé úsztatva az első gyűjtőhelyre, ahol fűrészmalomban végzik a feldolgozást. A vállalat elhatározta, hogy további fűrészmalmot állít üzembe néhány gyűjtőhelyen. Minden gyűjtőhelyről a fát a folyón lefelé haladva az első fűrészmalomba fogják szállítani.
A szállítási költség a megtett távolság és a tömeg szorzata. Ismerjük az egyes gyűjtőhelyek elhelyezkedését (az elsőtől vett távolságot km-ben) és azt, hogy mennyi fa keletkezik évente az egyes gyűjtőhelyeken. Kiszámítandó, hogy hova kell telepíteni az új fűrészmalmokat, hogy a szállítási összköltség a lehető legkisebb legyen.
Bemenet
Az első sor a gyűjtőhelyek N számát és az építendő új malmok K számát tartalmazza.
Ezután N sorban egy-egy számpár következik: az i. gyűjtőhely távolsága az elsőtől, majd az i. gyűjtőhelyen egy évben kitermelt fa tömege.
Kimenet
A minimális összköltséget kell megadni, és azt,
hogy ehhez melyik gyűjtőhelyeken kell beindítani az új malmokat.
Példa
| i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
| táv[i] |
0 |
2 |
3 |
6 |
7 |
20 |
22 |
34 |
35 |
44 |
57 |
66 |
88 |
100 |
| fa[i] |
1 |
2 |
3 |
44 |
5 |
6 |
33 |
18 |
9 |
10 |
11 |
2 |
13 |
44 |
válaszok
1 új malom esetén:
minimum = 3812;
új malom: 13
2 új malom esetén:
minimum = 1986;
új malmok: 7 13
3 új malom esetén:
minimum = 1332;
új malmok: 6 8 13
4 új malom esetén:
minimum = 804;
új malmok: 6 8 13 14
Teszadatok
Bemenet
Kimenetek
