最大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;
        }
05-18 15:11