生態(tài)系統(tǒng)開(kāi)更啦~【選必二】| 0基礎(chǔ)救星

關(guān)于數(shù)食物鏈的算法,圖論和動(dòng)態(tài)規(guī)劃可以輕松快速準(zhǔn)確地解決問(wèn)題;
首先我們定義所有相鄰箭頭指出的節(jié)點(diǎn)(一般是草)為“根節(jié)點(diǎn)”,定義所有相鄰箭頭指向的節(jié)點(diǎn)(一般是頂級(jí)捕食者,可以有多個(gè))為葉子節(jié)點(diǎn);
然后將母問(wèn)題劃分為小問(wèn)題,問(wèn)總食物鏈數(shù),可以為每一個(gè)節(jié)點(diǎn)設(shè)置一個(gè)屬性值,即為以該點(diǎn)為終點(diǎn)的食物鏈條數(shù),易證此問(wèn)題滿足無(wú)后效性。并且每個(gè)點(diǎn)的屬性值為所有指向他的節(jié)點(diǎn)的屬性值的總和;
最后,易得根節(jié)點(diǎn)屬性為1,向所有指向節(jié)點(diǎn)屬性值皆為已知的點(diǎn)遞推;
所有葉子結(jié)點(diǎn)的屬性值之和即為所求
標(biāo)簽: