11.3多校聯訓

Sol

先把操作序列讀入下來，然後把數存下來跑。

若要求出原式子計算結果，那就是一個棧，遇到操作符号就彈棧即可。再維護兩個棧分别表示讓棧頂元素為<code>0</code>或<code>1</code>的最小花費，一直做到最後即可。

注意字元串數組大小要開四倍。

Code

先想80分做法：枚舉所有點集判斷是否聯通，聯通則求出\(w\)的值。然後記搜枚舉子集求最值即可。時間複雜度\(O(m*2^n+3^n)\)。

100分做法真感覺不好想：設\(dp[i][j]\)表示\(i\)狀态下已經計算\(j\)個點的最小花費。那麼對于\(j&lt;size[i]\)，枚舉\(i\)中包含的一個非割點\(x\)，那麼有

\[dp[i][j]=\min_{x}\ dp[i-(1&lt;&lt;x)][j]

\]

對于\(j=size[i]\)，枚舉\(x\)以及先前個數\(k\)，那麼有

\[dp[i][size[i]]=\min_{x,k}\ dp[i-(1&lt;&lt;x)][k]+(size[i]-k)*w[i]

邊界值\(dp[1&lt;&lt;x][1]=0\)，表示初始感染點。最終答案就是\(dp[(1&lt;&lt;n)-1][n]\)。

肯定首先要求出原來樹的直徑，兩遍DFS基操求出長度以及路徑。

顯然一次修改肯定在直徑上。那麼新直徑隻可能是以下三種：修改邊斷開後兩個子樹各自的直徑，以及原直徑-原長+修改長。

符号化表達，就是\(D=\max (d[u],d[v],oldD-w_0+w)\)。當\(\max (d[u],d[v])-oldD+w_0&gt;w\)的時候，最值取在\(\max (d[u],d[v])\)裡面。而不等式左邊是一個常數，可以預處理。這一部分可以通過把直徑兩端分别作為跟跑兩遍樹形DP求得\(d\)，把處理出來的數列排序，二分查找\(w\)的位置，在該位置前面的答案就是\(\max\ oldD-w_0+w\)，後面的答案就是\(\max(d[u],d[v])\)，這兩部分都可以再用一個字首和預處理出來，兩式求最大值就是答案。時間複雜度\(O(n\log\ n)\)

寫了180行挂了。還沒調出來。

我是真沒想到8e8還能過，不然考場就寫70分了。

首先設\(da[l][r],db[l][r]\)表示區間\([l,r]\)中a，b的距離。設\(dis[l][r]=min(da[l][r],db[l][r])\)。

區間DP，設狀态\(dp[l][r][0/1/2]\)表示聯通了\(l,r\)的情況下，區間内任意一點到左/右/區間内另一點的最長長度。

二分答案\(x\)，剩下的賀題解：

我Sol都賀的，指望有代碼？？？