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
malomA.be
malomB.be
malomC.be
malomD.be
malomE.be
malomF.be
malomG.be
malomH.be
malomI.be
malomJ.be
malomK.be
malomL.be
malomB.be
malomC.be
malomD.be
malomE.be
malomF.be
malomG.be
malomH.be
malomI.be
malomJ.be
malomK.be
malomL.be