Албертаа дахь хотуудыг дөрвөлжин шугамтай цаасан дээр хойноос урд хүртлэхийг 0-ээс R-1 хүртэл дугаарлаж, баруунаас зүүн хүртлэхийг 0ээс C-1 хүртэл дугаарлан дүрслэж болох юм. Хот бүрийн чансааг тогтоосон байдаг ба тухайн нүд бүрт тухайн хотын чансааг илтгэх 1-ээс R*C тоог бичсэн байгаа. Чансаа нь 1 байвал хамгийн өндөр чансаа, R*C хамгийн муу. Хот төлөвлөлтийн газар дундаж чансаа хамгийн өндөр HxW хэмжээтэй тэгш өнцөгт газрыг сонгож авахыг хүсч байгаа. H W нь R C тоонуудаас тус бүр хэтрэхгүй сондгой тоонууд байх болно. Ямар нэгэн H W хэмжээтэй тэгш өнцөгт газрын хувьд дундаж чансааг дараах байдлаар тодорхойлно. Дундаж чансаа нь уг газрын аль нэг нүдэн дэх чансаа байх бөгөөд уг чансаанаас бага чансаатай нүдний тоо нь уг чансаанаас их чансаатай нүдний тоотой тэнцүү. Өөрөөр хэлбэл H W ширхэг тоог цувуулж бичээд эрэмбэлэхэд голын тоо нь гэсэн үг. Таны даалгавар бол бүх H W хэмжээтэй тэгш өнцөгт газрууд дотроос хамгийн сайн (утгаараа бага) дундаж чансааг олох rectangle(R,C,H,W,Q) процедурыг зохиох юм. Энд Q нь Q[a][b]-д орших хотын чансааг агуулсан массив юм.
R=5, C=5, H=3, W=3,
Q= 5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
rectangle(R,C,H,W,Q)=9
Дээрх жишээнд m=9 мөн бодлогын нөхцөлыг хангах хотуудыг дотруулсан байна.
Жишээ2:
R=2, C=6, H=1, W=5,
Q= 6 1 2 11 7 5
9 3 4 10 12 8
rectangle(R,C,H,W,Q)=5
No comments:
Post a Comment