一些想法：

??????? 現(xiàn)在是2024-3-15 06:01:22 哈哈卷死我可愛的舍友們~ 這兩天又想起來開學(xué)的時候立下的刷完kuangbin專題的flag（快進到干不完） 總是先把Acwing的提高課看完吧 每天這樣干一點總能干完的hhhhh，這會在喝npy買的奶茶，超多椰果真的好喝愛了愛了。

解題報告：

??????? 今天是最長上升子序列模型，模型本身難度不高，利用yxc的解題方法就可以分解為以下條件：

1. 集合表示方法： f[i] 表示從這一序列的第一項到第 i 項為止的所有可能的方案。

2. 集合表示屬性： 長度的最大值 總和的最大值

最核心的代碼如下：（按照題目條件稍加修改可以過掉下面兩道題）

?

for(int i = 1; i<=n ;i++)
{
    f[i]= 1;//賦初值 保證至少長度為1 即本身
    for(int j =1 ;j<i ;j++)
    {
        if(a[i] > a[j]) f[i] = max(f[i], f[j]+1);
    }
}

AcWing 1017. 怪盜基德的滑翔翼

AcWing 1014. 登山

??????? 然后是幾道需要將原題目轉(zhuǎn)化為最長上升子序列模型的題目。

????????合唱隊形求一個帶峰值的最長隊伍，我們可以通過將每個人視為以他為左上升的子序列的右端點的同時視作右上升的子序列的左端點來找到最大的一個目標隊形，記得減去被重復(fù)計算的這個人本身。

??????? 友好城市求最多可以批準的城市數(shù)量，思考形成最長上升子序列的過程，只有在當(dāng)前考慮的一層循環(huán)的值的左邊的值，即序號比它小的值才可以被考慮是否可以用來更新最大值。友好城市就是如此，我們將河岸一邊的城市進行正序排序，只有當(dāng)另一邊的建橋方案無沖突即也是正序時才是合法方案，那么可以使用pair來保證只使用兩個序號都比這一組小的值來更新最大方案。

??????? 最大上升子序列和比較簡單，是對模型的變形，從求最長的子序列變成最大的子序列。

AcWing 482. 合唱隊形

AcWing 1012. 友好城市

AcWing 1016. 最大上升子序列和

??????? 隨后是兩道劇情連續(xù)的題目。（痛苦降臨）

??????? 攔截導(dǎo)彈。第一問就是最長上升子序列。第二問用貪心思路，從前往后掃描每個數(shù)，對每個數(shù)做判斷，如果不存在比它小的數(shù) (一個新的最大值) 那么就新開一個子序列 (新的系統(tǒng))，如果存在，則找到一個結(jié)尾比它大的數(shù)列，放在這個數(shù)的后面 (可以通過二分優(yōu)化) 。最后第一問輸出最長的序列的長度，第二問輸出創(chuàng)建的系統(tǒng)總數(shù)即可。

??????? 導(dǎo)彈防御系統(tǒng)。迭代加深，利用一個dfs參數(shù)depth來記錄上升系統(tǒng)與下降系統(tǒng)的和。從depth=1開始，不斷depth++直到得到一個合法的能包容上升與下降系統(tǒng)的和的解。

????????dfs過程中，暴力搜索將每個元素放到上升那一坨還是下降那一坨系統(tǒng)中

????????當(dāng)滿足第一個比新加入的元素的（上升或下降系統(tǒng)的）條件就把這個元素加進去，與上一題的貪心解法是相同的

????????如果沒找到這樣一個放入的方法的解，那么就拓寬隊列的長度，直到放入上升和下降都不行的話，那么返回false

??????? 看代碼會好理解一點，懶得寫了（bushi）

AcWing 1010. 攔截導(dǎo)彈

AcWing 187. 導(dǎo)彈防御系統(tǒng)

??????? 最后是一道組合題，求最長公共上升子序列。

??????? 本題使用公共子序列的狀態(tài)表示， f[i][j] 表示 a 的前 i 個元素中和 b 的前 j 個元素中，以b[j] 為結(jié)尾的方案，存的是方案中的上升子序列的長度的最大值。

??????? 將方案話劃分為：

??????? 1. 不選 a[i] 的子集 直接符合定義 f[i-1][j]

??????? 2. 選了 a[i] 的子集 前提是a[i] ==? b[j]

??????????????? 然后確定最大值的轉(zhuǎn)移，當(dāng) b[k] < b[j] (滿足上升條件)時 才能用來更新最大值，然后我們 要求這些前 1~j-1 中的最大值。

??????? 時間復(fù)雜度上 狀態(tài)表示為 狀態(tài)計算為 n 所以總的時間復(fù)雜度是

????????注意到我們在狀態(tài)計算的時候，求的來的 b[1~j] 的最大值是前綴最大值，在往后計算時會重復(fù)計算，也即最大值會在計算 b[1] 開始向后傳遞，同時 只有當(dāng)這個數(shù)已經(jīng)小于我們現(xiàn)在正在看的 a[i] 時才能加入計算前綴最大值的行列中，所以我們開一個值 maxv ，當(dāng) a[i]>b[j] 時就記錄這樣的前綴最大值即可。

優(yōu)化前：

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (a[i] == b[j])
        {

            int maxv = 1;
            for (int k = 1; k < j; k ++ )
                if (b[j] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);

            f[i][j] = max(f[i][j], maxv);
        }
    }

優(yōu)化后：

    for (int i = 1; i <= n; i ++ )
    {
        int maxv = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

心得：

??????? 兩道導(dǎo)彈題目當(dāng)初學(xué)的時候真是要了老命，寫這篇博客的時候還琢磨了一個鐘，還是太菜（幸好最后搞懂了）。首次遇到了迭代加深的題，多看多學(xué)。

????????文章來源地址http://www.zghlxwxcb.cn/news/detail-849647.html

到了這里，關(guān)于動態(tài)規(guī)劃—— 最長上升子序列模型 解題記錄的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！