最大點獨立集+DP

答案就是在圖中選出一些點，使得兩兩不可達且權值和最大。

然而并沒有找到證明，于是只好自己腦補。大概是會證(口)明(胡)了吧……現給出我的證明如下：

先分析出行進的策略：走到第一行最右的一個非零格子，向下走一行進入第二行，走到右邊最右的一個非零格子(若無則不走)，向下走一行進入第三行，走到右邊最右的一個非零格子(若無則不走) ……走到右下角。

證明：易知選出的點集中最右上的(稱作x)那個一定在第一遍的行進路上。只需證明當x的權值減完之后，點集S中除x以外的最右上的點(稱作y)在接下來的行進路上，即可說明存在這樣一種方案。

首先，顯然x，y圍成的矩形內(不含邊界)中不可能有點，否則加入點集更優。假設y無法進入當前行進路，即y的右上角還有點，設為u。易知這個點不會在x的右上方，否則就不會輪到x。這個點只能在[y的右上]與[x的左上或右下] 的交集之中。此時用u替換x，點集S權值更優。但可能導致u和x的前一個點集中的右上的點無法銜接，即變得可達。設x的前一個點集中的右上點為z。如果z一直都在消u，則把z也丟掉即可。如果z消u之前在消v(即v,u不可達,v不屬于點集S)，則用v,u共同替換x,z答案更優，此時繼續遞歸尋找z的右上點，變成子問題。點集S中最右上的點沒有右上點，因此子問題可以結束，即可以找到最優解。

可能你看不懂我在說什么，建議把圖畫出來比一比，那樣應該就知道了QAQ