AC代碼

https://codeforces.com/contest/1740/submission/178643201

題意：

Pak Chanek必須執(zhí)行以下操作n次，同時(shí)保持序列s（最初為空）：

1. 選擇一張牌x，條件不會(huì)有其他牌掛在上面。

2. 將寫在卡片x上的數(shù)字附加到s的末尾。

3. 如果x≠1，且卡px上的數(shù)字大于卡x上的數(shù)值，則將卡px中的數(shù)字替換為卡x中的數(shù)值。

4. 取出卡x。

求最后序列s中的非遞減序列的長(zhǎng)度最大值。

題解：

樹形DP

? ?對(duì)于當(dāng)前節(jié)點(diǎn)，所有的子節(jié)點(diǎn)有兩種選擇：

? ?1. 其子樹根的值會(huì)上傳，同時(shí)子樹節(jié)點(diǎn)值可以形成非遞減序列

? ? 2. 不上傳子樹根值，同層次子樹節(jié)點(diǎn)值可以形成非遞減序列

dp[0][cur] 表示其子樹根的值會(huì)上傳，同時(shí)子樹節(jié)點(diǎn)值可以形成非遞減序列的長(zhǎng)度? ? ??

? ? dp[1][cur] 表示不上傳子樹根值，同層次子樹節(jié)點(diǎn)值可以形成非遞減序列的長(zhǎng)度