АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Аалис Боб-д 1х1 модон нүднээс бүрдсэн хавтан өгөөд хамгийн бага зардлаар хавтангийн 1х1 нүд бүрийг салгаж авах даалгавар өгсөн. Хавтанг хуваахдаа Боб босоо болон хөндлөн шугамын дагуу хуваах ёстой.

Хавтанг нүднүүдэд хуваахын тулд Боб хөндлөн болон босоо шугамын дагуу бүтэн хавтанг хуваах хэрэгтэй. Хавтанг босоогоор эсвэл хөндлөнгөөр хугалах гарах зардал нь  cost_y[i] эсвэл cost_x[j]-г хэдэн тусдаа хавтан хуваасан тоогоор гарна. Хавтанг 1х1 нүднүүд болгон хуваахад гарах зардал нь хавтанг хуваах бүрд гарсан зардлуудын нийлбэр. Боб-д хамгийн багадаа ямар зардлаар хавтанг хуваахыг олж өгнө үү? Хариулт том тоо байж магадгүй тул хариуг 10⁹+7 д хуваагаад үлдэгдлийг хэвлэнэ үү.

Жишээ нь

2х2 хавтан байсан ба босоогоор хугалах зардал нь $3 ба хөндлөгөөр хугалах зардал нь $1 байг. Эхлээд 1 ба 2-р нүднүүдийн хооронд хөндлөнгөөр нь хуваавал зардал нь $3. Эхний хугалалтын дараа ­2 тусдаа хавтан бий болох ба хавтан тус бүрийг босоогоор нь хугалахад $1-ийн зардал гарах ба нийт $2-ийн зардал гарна гэсэн үг. Ингээд нийт 2х2 хавтанг 1х1 нүднүүдэд хуваах зардал нь $3x1+$1х2=5 болно. 5%(10⁹+7)=5.

Функцийн тайлбар

boardCutting гэдэг функцийг бичнэ үү. Бүхэл тоо хэвлэх үүрэгтэй.

boardCutting доорх өгөгдөлийг хүлээн авна

• Cost_x: бүхэл тоон массив, босоо хуваалтын зардал
• Cost_у: бүхэл тоон массив, хөндлөн хуваалтын зардал

Оролтын бүтэц

Эхний мөрөнд бүхэл тоо , q , тестийн тоо

Дараагийн q  мөрөнд:

• Эхний мөрөнд 2ш эерэг бүхэл тоо , n ба m , хавтангийн урт болон өргөн
• Хоёр дахь мөрөнд m-1 ширхэг бүхэл тоон массив cost_y өгөгдөнө. Cost_y[i] нь мөр [i] болон [i+1] хооронд хөндлөнгөөр нь хугалахад гарах зардал
• Гурав дахь мөрөнд  n-1 ширхэг бүхэл тоон массив cost_x өгөгдөнө. Cost_x[i] нь багана [i] болон [i+1] хооронд босоогоор нь хугалахад гарах зардал

Хязгаарлалт

1 <= q <= 20

2 <= n, m <= 1000,000

0 <= cost_y[i], cost_x[i] <= 10⁹

Гаралтын бүтэц

Тест бүрт хавтанг 1х1 нүднүүд болгож хуваахад зарцуулагдах хамгийн бага зардлыг олоод хариуг 10⁹+7 д хуваагаад үлдэгдлийг хэвлэ.

Жишээ оролт

 1

2 2

2

1

Жишээ гаралт

4

Тайлбар

2х2 хавтан өгөгдсөн ба cost_y[1]=2, cost_x[1]=1. Эхний хуваалтыг y[1] болон y[2]-ийн дундуур хөндлөнгөөр хуваана.  Ингэснээр $2 зарцууллаа (Тэр нь хамгийн өндөр өртөгтэй хуваалт учраас эхэлж хуваана.) Дараагийн удаад x[1] зардлаар буюу босоогоор 2 ширхэг 1х2 хэмжээтэй хавтангаа хуваана. Хуваалт тус бүр $1 өртөгтэй тул $1x2=$2 зардал гарна. Ингээд манай хариу mincost=(($2x1)+($1x2))%(10⁹+7)=4.

Жишээ оролт

 1

6 4

2 1 3 1 4

4 1 2

Жишээ гаралт

42

Тайлбар

Дараах дарааллаар хавтанг хуваана: y[5], x[1], y[3], x[3], y[2], y[4], ба x[2].

Хуваалт 1: Хөндлөнгөөр cost_y[5]=$4; 1 ширхэг хавтан. Нийт зардал = $4x1=$4.

Хуваалт 2: Хөндлөнгөөр cost_x[1]=$4; 2 ширхэг хавтан. Нийт зардал = $4x2=$8.

Хуваалт 3: Хөндлөнгөөр cost_y[3]=$3; 2 ширхэг хавтан. Нийт зардал = $3x2=$6.

Хуваалт 4: Хөндлөнгөөр cost_y[1]=$2; 2 ширхэг хавтан. Нийт зардал = $2x2=$4.

Хуваалт 5: Хөндлөнгөөр cost_x[3]=$2; 4 ширхэг хавтан. Нийт зардал = $2x4=$8.

Хуваалт 6: Хөндлөнгөөр cost_y[2]=$1; 3 ширхэг хавтан. Нийт зардал = $1x3=$3.

Хуваалт 7: Хөндлөнгөөр cost_y[4]=$1; 3 ширхэг хавтан. Нийт зардал = $1x3=$3.

Хуваалт 8: Хөндлөнгөөр cost_x[2]=$1; 6 ширхэг хавтан. Нийт зардал = $1x6=$6.

Нийт зардал = 4+8+6+4+8+3+3+6=42. Хариу 42%(10⁹+7)=42.

Орчуулсан : Б.Мөнхбаяр АНУ