題意 : 給定兩數列$A$和$B$，可任意次(包括$0$次)將任一個A中某項替換成$B$中某項，$B$中每項只能替換一次，問操作後的最大連續子陣列

按照貪心的想法，優先使用$B$中較大的一定更優，證明顯然(在最優情況下，如果替換的$B$元素是固定的，那先後順序不會影響答案，因為用了都用了，若不及早使用比較優的$B$中元素，錯過了使用時機，反而沒辦法得到最佳解)

所以先將$B$由大到小排個序。

接著定義$dp(i,j)$為使用B陣列前$i$個，$A_1,A_2_,\dots,A_j$的最大連續子陣列，分四種情況轉移

1. 選擇$A_j$後如果最大和$<0$，那乾脆不拿更優，因此從0轉移

2. 選擇以$B_i$替換$A_j$，因此從$dp(i-1,j-1)+B_i$轉移

3. 選擇$A_j$，不替換，因此從$dp(i,j-1)+A_j$轉移

把$dp(0,x)$的部分先處理好，之後好好轉移，每次轉移時順便紀錄最大即可

時間複雜度 : $O(KlogK + NK)$

空間複雜度 : $O(NK)$ 滾動優化後可 $O(N)$

程式 : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a267.cpp

題意 : 給定兩數列$A$和$B$，可任意次(包括$0$次)將任一個A中某項替換成$B$中某項，$B$中每項只能替換一次，問操作後的最大連續子陣列

 

按照貪心的想法，優先使用$B$中較大的一定更優，證明顯然(在最優情況下，如果替換的$B$元素是固定的，那先後順序不會影響答案，因為用了都用了，若不及早使用比較優的$B$中元素，錯過了使用時機，反而沒辦法得到最佳解)

所以先將$B$由大到小排個序。

接著定義$dp(i,j)$為使用B陣列前$i$個，$A_1,A_2_,\dots,A_j$的最大連續子陣列，分四種情況轉移

1. 選擇$A_j$後如果最大和$<0$，那乾脆不拿更優，因此從0轉移

2. 選擇以$B_i$替換$A_j$，因此從$dp(i-1,j-1)+B_i$轉移

3. 選擇$A_j$，不替換，因此從$dp(i,j-1)+A_j$轉移

把$dp(0,x)$的部分先處理好，之後好好轉移，每次轉移時順便紀錄最大即可

時間複雜度 : $O(KlogK + NK)$

空間複雜度 : $O(NK)$ 滾動優化後可 $O(N)$

 

程式 : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a267.cpp

痾 latex 跟 markdown 都燒雞

想像一下 證明顯然上面有刪除線

壞掉那邊是 $A_1,A_2,...,A_j$