算法合集之基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問(wèn)題(編輯修改稿)
2024-11-12 20:32 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ( ( ) ) ) ( 0：無(wú)插頭狀態(tài)，用 表示 1：左括號(hào)插頭，用 ( 表示 2：右括號(hào)插頭，用 ) 表示 3進(jìn)制 (1 1 2 0 2 1 2)3 狀態(tài)的轉(zhuǎn)移 ? 每次轉(zhuǎn)移相當(dāng)于輪廓線上當(dāng)前決策格子的左插頭改成下插頭，上插頭改成右插頭的狀態(tài)． Case 1 沒(méi)有上插頭和左插頭，有下插頭和右插頭，相當(dāng)于 構(gòu)成一個(gè)新的連通塊 ． ) 插頭 ( 插頭 ( ) ( ( ) ) 轉(zhuǎn)移時(shí)間： O(1) Case 2 有上插頭和左插頭，這種情況下相當(dāng)于 合并兩個(gè)連通分量 預(yù)處理每個(gè)狀態(tài)每的括號(hào)所匹配的括號(hào) 轉(zhuǎn)移時(shí)間 : O(1) ( 插頭 (插頭 ( ( ) ) ( ( ) ( 插頭 Case 上插頭和左插頭均為 (插頭 Case 2 有上插頭和左插頭 轉(zhuǎn)移時(shí)間： O(1) ( ) ( ) ( ) ( 插頭 )插頭 Case 左插頭為 )插頭，上插頭為 (插頭 Case 2 有上插頭和左插頭 ( 插頭 )插頭 路徑的兩端連接起來(lái)形成回路 Case 左插頭為 (
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1