[CF 513E1,E2] Subarray Cuts

作法：

首先把題目改為：求 $\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$ 的最大值，因為可以簡單證明前式達到最大值若且唯若題目要求的式子達到最大值，具體來說是因為如果上式中其中一項是負的話，就顯然不會是最大值了，因此最大值發生在每項都是正的情形，也就和加了絕對值沒兩樣了。而轉換成 maximize 這個函式的話就可以用DP了：記 $dp[i][j][c]$ 代表在$a_1,a_2,...,a_i$中取 $j$ 段連續的數，假設他們的和分別為$s_1,...,s_j$，則其值為$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{j-1}-s_j) + c\cdot s_j$ 的最大值，其中$c = 1,-1$（實作上是用 $0$ 來代表 $c=-1$，因此這裡都把下標寫為$-1$）。但這邊要注意到 $j=k$ 時會不太一樣，他的值應該要是$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$（不管 $c$ 為多少），而這可以在轉移的時候多加留意就好了。

因此再來要看如何轉移，首先$dp[i][j][c]$當然可以轉移到$dp[i-1][j][c]$，也就是$s_j$裡面不包含$a_i$的情形。而如果有包含，那麼就可以轉移到$dp[i-r][j-1][-1]+(c+1)\cdot (a_{i-r+1}+...+r_i)$，或是$dp[i-r][j-1][1]+(c-1)\cdot (a_{i-r+1}+...+r_i)$。這邊要注意到這是$j\neq 1$且$j\neq k$時的轉移式，當$j=1$時轉移到$dp[i-r][j-1][-1]$的總和那項的前面係數必須是 $c$，而轉移到$dp[i-r][j-1][1]$ 的係數也一樣是$c$。至於$j=k$時兩個係數則分別為$1$和$-1$，這些都可以由前面$dp$值的定義得出。因此這樣就得到了一個$O(n^2k)$的算法了，直接DP就可以了，code 為下面的第一份 code。

接下來我們要想辦法把他改進成$O(nk)$的，而對於這種轉移式通常就是維護某種前綴的$max$值，使得到時候在算好幾個數的$max$值的時候可以直接$O(1)$得知。這裡以$dp[i][j][1]$為例，當他想轉移到$dp[i-r][j-1][-1]$時，我們會需要以下所有數的$max$值：
$\begin{cases}dp[i-1][j-1][-1]+2a_i\\dp[i-2][j-1][-1]+2(a_{i-1}+a_i)\\dp[i-3][j-1][-1]+2(a_{i-2}+a_{i-1}+a_i)\\ \;\;\;\;\;\;\;\;\;\;\;\;\; \vdots\end{cases}$
因此可以想到直接令一個陣列$g[i][j]$等於上面那一陀值，那麼就可以得到$g$的轉移式為；$g[i][j]=max(g[i-1][j],dp[i-1][j-1][-1])+2\cdot a_i$，因此可以在一算完$dp[i][j][-1]$的時候就馬上計算$g[i+1][j+1]$的值，這樣之後要算$dp[i+1][j+1][1]$時就可以$O(1)$轉移了。

但上面只是其中一個情形，也就是「要算$dp[i][j][1]$且他想要轉移到$dp[i-r][j-1][-1]$時所得到的值」，實際上我們總共會需要$8$個$g$陣列，因為還要有「要算$dp[i][j][-1]$」時所需要的值，還有不要忘了前面的轉移式中有$c-1$和$c+1$，也就是上面那陀$max$中右邊累加和的係數也可能有其他值，因此必須對每種情形都紀錄一個$g$陣列。不過他們的轉移都一樣，所以可以直接用個 for 把所有的$g$值一起更新。

code(E1):

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=30000+10 , maxk=200+10 ;
 
int a[maxn] ;
int dp[maxn][maxk][2] ;
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , a[i]+=a[i-1] ;
    fill(dp[0][0],dp[n][k]+2,-INF) ;
    dp[0][0][0]=dp[0][0][1]=0 ;
    for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) for(int c=0;c<2;c++)
    {
        int &x=dp[i][j][c] ;
        if(!j){x=0 ; continue ;}
        x=max(x,dp[i-1][j][c]) ;
        int c1=(c==0 ? 0 : 2) , c2=c1-2 ;
        if(j==1) c1-- , c2++ ;
        else if(j==k) c1=1 , c2=-1 ;
        for(int r=1;r<=i;r++)
            x=max(x,dp[i-r][j-1][0]+c1*(a[i]-a[i-r])) ,
            x=max(x,dp[i-r][j-1][1]+c2*(a[i]-a[i-r])) ;
    }
    printf("%d\n",max(dp[n][k][0],dp[n][k][1])) ;
}
 

code(E2):

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=30000+10 , maxk=200+10 ;
 
int a[maxn] ;
int dp[maxn][maxk][2],g[maxn][maxk][2][5] ;
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , a[i]+=a[i-1] ;
 
    fill(dp[0][0],dp[n][k]+2,-INF) ;
    fill(g[0][0][0],g[n][k][1]+5,-INF) ;
    dp[0][0][0]=dp[0][0][1]=0 ;
    for(int i=0;i<2;i++) for(int j=-2;j<=2;j++)
        g[1][1][i][j+2]=j*a[1] ;
 
    for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) for(int c=0;c<2;c++)
    {
        int &x=dp[i][j][c] ;
        if(!j) x=0 ;
        else
        {
            x=max(x,dp[i-1][j][c]) ;
            int c1=(c==0 ? 0 : 2) , c2=c1-2 ;
            if(j==1) c1-- , c2++ ;
            else if(j==k) c1=1 , c2=-1 ;
            x=max(x,g[i][j][0][c1+2]) ;
            x=max(x,g[i][j][1][c2+2]) ;
        }
 
        if(c==0) for(int r=-1;r<=2;r++)
            g[i+1][j+1][0][r+2]=max(g[i][j+1][0][r+2],x)+r*(a[i+1]-a[i]) ;
        else for(int r=-2;r<=1;r++)
            g[i+1][j+1][1][r+2]=max(g[i][j+1][1][r+2],x)+r*(a[i+1]-a[i]) ;
    }
    printf("%d\n",max(dp[n][k][0],dp[n][k][1])) ;
}