"Гар барилт" бодлогын бодолт

2 ч хүн энэ бодлогын бодолтыг асуусан байсан. Өгүүлбэр
Динамик програмчлал буюу DP-н гоё бодлого, Монголд оюутан байхдаа өөрөө бол бодож чаддаггүй л байсан санагдаж байна.

Бодолт:
2n хүмүүс байгаа гэж үзье. Аль нэг O цэг/хүнийг сонгож аваад аль аль хүнтэй гар барьж болохыг судлаж үзье. Ямар ч байсан уг O цэгээс өөр тохирох хүнтэй гар барингуут тухайн шулуун нь дугуй ширээг буюу өөрөөр хэлбэл уг 2n цэгийг хоёр хэсэгт хуваана. Ингэхдээ уг хоёр хэсэгт байгаа цэгүүдийн тоо заавал тэгш байх ёстой бас. Цаашаа жаахан бодоод үзэхээр O цэг/хүнтэй гар барьж болох цэгүүдийн/хүмүүсийн тоо нь яг n ширхэг байгаа.

Одоо дан шулуунаар яриад явая. Дээр О цэгээс эхлэлтэй шулуун бүр 2n цэгүүдийг дандаа ялгаатай хэсэгт хуваана, мөн хуваагдсан хэсэг бүрийг дахин дугуй ширээн дээрх хүмүүс мэтээр сэтгээд дэд бодлого болгоод бодно. Тэгвэл аль нэг дээрх шулууныг татахад хуваагдсан хоёр талд тус бүр хичнээн цэгүүд байх ёстойг мэдэх хэрэг гарна. Хэрвээ мэдчихвэл манай бодлогын хариу уг хоёр дэд бодлогын үржвэрүүдээр нэмэгдэх ёстой. Сайн бодож хараарай.

О цэгээс татсан шулууны боломжит нөгөө цэгүүдийг нь K гэе. 0<=K<=n-1, тэгвэл хуваагдсан хоёр талын цэгүүдийн тоо нь тус бүр 2*K, 2*(n-K-1) байна. Тус бүр эдгээр тооны цэгүүдтэй дугуй ширээн дээр суусан хүмүүсийн гар барилтын тоог мэдэж чадвал бодлогын хариу маань уг гар барилтын тоонуудын нийлбэр байна. Дэд бодлогот хэрхэн хувааж байгааg хараарай.
f(n)-ээр n хүмүүс дугуй ширээнд суухад хичнээн гар барилт байгааг тэмдэглэе. Тэгвэл
f(n) += f(2k)*f(2(n-k-1)), k=(0..n-1) байна. Энд нэг гарах ёстой асуулт бол ингэж хоёр хувааж байхад хуваагдсан хэсэгт яаж хуваах нь хамаатай биш билүү? үүнийг тооцох ёстой биздээ? бодолт/тоолот дутуу юм бишүү? гэсэн асуулт гарна. Сайн бодоо үз, өмнөх дэд бодлогын бодолтод тоологдцон байгаа.

Бодлогын бодолтыг C++ дээр доорх линк-ээр орж сонирхоорой(f(n)-ээр огтлоогүй шулуунуудын тоог тэмдэглэж бодсон байгаа, ялгаагүй бодолт).

Source

QonR

Сайн байцгаана уу
Одоо хэсэгтээ шинэ пост оруулахгүй байх, гэхдээ асуух бодлого, сонирхож хэрэг болсон алгоритм байвал baasanbatp@gmail.com хаягруу явуулвал аль болох хурдан зав гаргаад хариу бичиж эсвэл хэрэгтэй гэж үзвэл энд постоор тайлбарлаж байна аа.