最大子段和之M子段和

最大M子段和

题目模型

• N个整数组成的序列 \(a_1,a_2,a_3,…,a_n\) ，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。

问题分析

• 方法一：

  • 看到序列，我们首先要尝试用线性dp去处理，线性dp经典状态定义:f[i][j]，i一般表示序列的前i个元素，j表示限制，这里表示划分了j个不相交的子段，我们还需要对i进行进一步的定义，即是否包含第i项，因为对当前元素a[i]来说，要么单独成一个子段，要么和最后一个子段合并，所以必须包含第i个元素。

  • 动态转移方程：dp[i][j]=max(dp[i-1][j],dp[k][j-1])+a[i] (j-1<=k<i)。

  • Code

    #include <bits/stdc++.h>
    const int maxn = 1e3+3,Inf=0x3f3f3f3f;
    typedef long long LL;
    int a[maxn],dp[maxn][maxn];
    void Solve(){
        int n,m;scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;++i){//前i个元素
            for(int j=1;j<=std::min(i,m);++j){//划分出j个子段
                if(i==j)dp[i][j]=dp[i-1][j-1]+a[i];//显然
                else{
                    int temp=dp[i-1][j];//把a[i]直接并到最后一子段
                    for(int k=j-1;k<i;++k)//枚举上一个状态的最后一个子段的右端点，a[i]单独作为一个子段
                        temp=std::max(temp,dp[k][j-1]);
                    dp[i][j]=temp+a[i];
                }            
            }
        }    
        int ans=-Inf;
        for(int i=m;i<=n;++i)
            ans=std::max(ans,dp[i][m]);
        printf("%d\n",ans);
    }
    int main(){
        Solve();
        return 0;
    }
    

  • 时间效率为：\(O(n^3)\) ，空间效率为：\(O(m*n)\)。

• 方法二：

  • 我们尝试对方法一的dp阶段和状态进行修改， 即把子段限制数M作为阶段，即状态dp[i][j]表示把序列前j分成i个子段且包含a[j]的最大子段和。

  • 动态转移方程有：dp[i][j]=max(dp[i][j-1],dp[i-1][k])+a[j] (i-1<=k<j)。

    • dp[i][j-1]+a[i]：表示合并到最后一个子段里

    • dp[i-1][k]+a[i]：表示前k元素挑出k个子段，所以k>=j-1，然后a[i]单独的子段。

    • 此动态转移方程同样满足无后效性和最优子结构。

    • 我们把问题的所有状态记录下来形成一个二维矩阵，显然当前状态只跟它上一行和左边的状态有关，我们可以把空间效率压掉以为变成 \(O(n)\) 。

    • 同时上一行的状态只有在当前状态前面的最大值对转移有用，我们可以在遍历当前行时维护一下上一行的最大值，这样时间效率就压掉了一个n,变成\(O(n*m)\)。

    • Code

      #include <bits/stdc++.h>
      typedef long long LL;
      const int maxn = 1e4+5;
      const LL Inf=0x3f3f3f3f3f3f3f3f;
      LL a[maxn],dp[2][maxn];
      void Solve(){
          int n,m;scanf("%d%d",&n,&m);
          for(int i=1;i<=n;++i)
              scanf("%lld",&a[i]);
          int k=1;//滚动数组指针，k表示当前行，!k表示上一行
          for(int i=1;i<=m;++i,k=!k){//枚举区间个数
              LL Max=-Inf;
              for(int j=i;j<=n;j++){
                  Max=std::max(Max,dp[!k][j-1]);//记录前j-1,分成i-1个区间时最大值
                  if(i==j)
                      dp[k][j]=dp[!k][j-1]+a[j];
                  else//要么是a[j]单独成一个区间，此时为Max+a[j]，或者直接合并为dp[k][j-1]+a[j]
                      dp[k][j]=std::max(Max,dp[k][j-1])+a[j];         
              }
          }
      
          LL ans=-Inf;
          for(int i=m;i<=n;++i)//!k行才记录的是第m行的状态
              ans=std::max(ans,dp[!k][i]);
          printf("%lld\n",ans);
      }
      int main(){
          Solve();
          return 0;
      }
      

• 方法三

  • 方法二把空间优化到线性，时间优化到\(O(n^2)\) ，但如果 \(n\) 和 \(m\) 高达 \(10^5\)显然dp是无法解决了。比如：51nod 1115 最大M子段和 V3

  • 对这个问题我们先对原数组进行处理，然后利用可撤销贪心解决。

    • 首先把原数组连续的正数加起来变成一个数，连续的负数加起来变成一个数，0加到哪里都一样，这样我们就得到了一个正负交替的环形序列。

    • 如果新的环形序列里正数的个数为cnt，所有正数之和为ans则存在两种情况：

      1. \(cnt<=M\)，因为可以选空，所以答案就是所有正数之和ans。
      2. \(cnt>M\) ，此时ans包含了cnt个正数区间，所以我们需要通过操作减少cnt-M个区间。

    • 对于情况2，我们可以通过两种操作减少区间：

      1. 删除一个正数(ans包含所有正数之和，删除一个正数相当于减少了一个区间).
      2. 将一个负数与它两边的正数合并，相当于把两个正数区间合并成了一个区间，也减少了一个区间。

    • 很容易能想到一个贪心思想，即每次选择最小的正数删除一个区间，或选择最大一个负数与它两边的正数合并减少一个区间。

    • 但这个贪心是不正确的，因为删除一个较小的正数是在减少一个区间的最优，但有可能不删除这个正数，而是通过若干次合并在减少多个区间。

      • 例如：序列10 -4 3 -4 8 -100其中M=1，根据刚才的贪心策略，我们先删除3，减少了一个区间，然后最大的负数为-4，此时因为3已经被删除-4就无法合并了。为了解决类似的问题，我们要用到可撤销的贪心思想。

    • 实现步骤：

      1. 把序列中正数均变成负数，并把数都压入大根堆。
      2. 套用可撤销贪心思想，做cnt-M次即可，具体见代码。

    • Code

      #include <bits/stdc++.h>
      typedef long long LL;
      const int maxn=2e5+5;
      struct Node{
          int id;
          LL w;
          Node(){};
          Node(int x,LL y){id=x;w=y;}
          bool operator <(const Node &a)const{
              return w<a.w;
          }
      };
      int n,m,N=0,L[maxn],R[maxn]; 
      LL ans=0,a[maxn],b[maxn];
      std::priority_queue<Node> q; 
      bool flag[maxn];
      void Init(){
          scanf("%d%d",&n,&m);
          for(int i=1;i<=n;++i){
              scanf("%lld",&a[i]);//原始数组
              if(!N || (a[i]>=0)!=(b[N]>=0))
                  b[++N]=a[i];//新数组，上个数和当前数符号不一样节点++ 
              else
                  b[N]+=a[i];//符号一样，累加
          }
          if((b[1]>=0)==(b[N]>=0))//因为是环，b[1]和b[N]同号就合并
              b[1]+=b[N--];//合并后新数组个数减一，记得N--
      }
      void Solve(){
          Init(); 
          int tot=0;//记录正数个数
          for(int i=1;i<=N;++i){//遍历新数组，压入大根堆
              L[i]=i-1; R[i]=i+1;//初始化i的左右邻居
              if(b[i]>0){//正数累加到答案，然后变负
                  ans+=b[i]; b[i]=-b[i]; tot++;
              }
              q.push(Node(i,b[i]));
          }
          R[N]=1; L[1]=N;//注意是环形
          if(m>=tot){//正数个数小于m，则全部选
              printf("%lld\n",ans);return;
          }
          m=tot-m;//正数大于m则合并或删除tot-m个区间
          while(m--){
              Node t=q.top(); q.pop();
              int i=t.id;
              if(flag[i]){++m; continue;}
              else{//可撤销贪心
                  ans+=b[i];
                  flag[L[i]]=1;
                  flag[R[i]]=1;
                  b[i]=b[L[i]]+b[R[i]]-b[i];          
                  R[L[L[i]]]=i;
                  L[R[R[i]]]=i;
                  q.push(Node(i,b[i]));//压入新点         
                  L[i]=L[L[i]];
                  R[i]=R[R[i]];           
              }
          }
          printf("%lld\n",std::max(0LL,ans));
      }
      int main(){
          Solve();
          return 0;
      }