给定由 n 个整数 (可能为负) 组成的序列 a1,a2,a3...,an,
以及一个正整数 m, 要求确定序列的 m 个不相交子段, 使这 m 个子段的总和最大!
特别注意:
有些题目可能不存在负数答案, 给出的序列全是负数, 那么不管 m 是多少, 答案是 0. 此时选择的子段是 0 个, 不足 m 个, 但符合题意...
也可能有些题目要求, 必须选够 m 个子段.
区别在 dp 数组的初始化. 前者要求 dp 初始为 0, 后者要求第 0 行为 0, 其余为负无穷
解题思路:
动态规划, 借助矩阵可以直观的看到计算过程.
定义二维数组 dp, dp[ i ][ j ], 表示前 j 项所构成 i 子段的最大和, 且必须包含着第 j 项, 即以第 j 项结尾
然后是一个递推过程.
求 dp[ i ][ j ], 有两种情况:
1,dp[ i ][ j ] = dp[ i ] [ j-1 ] + a[ j ] , 即把第 j 项融合到第 j-1 项的子段中, 子段数没变
2,dp[ i ][ j ] = dp[ i-1 ] [ t ] + a[ j ],(i-1<= t <j )
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=1e6+5;
- const int INF=0x3f3f3f3f;
- int n,m;
- ll a[N],dp[2][N]; // 只保存上一行和当前行
- int main()
- {
- while(~scanf("%d%d",&n,&m)) //n 个数字, m 子段和
- {
- for(int i=1;i<=n;i++)
- scanf("%lld",a+i);
- for(int i=0;i<=n;i++)
- dp[0][i]=0,dp[1][i]=0; // 关键! 此题答案只允许正值
- for(int i=1,k=1;i<=m;i++,k^=1) // 分为 i 段, k 为两行之间的切换
- {
- dp[k][i-1]=-INF; //i==j 时, 杜绝与前一元素共 5
- ll maxpre=-INF; //maxpre 记录上一行的最大值
- for(int j=i;j<=n-m+i;j++)
- {
- maxpre=max(maxpre,dp[k^1][j-1]); // 随时更新上一行最大值
- dp[k][j]=max(dp[k][j-1],maxpre)+a[j]; //* 对情况 1,2 的选择
- // 如果 a[j]是负数的话, 也是不会影响 maxpre 的. 因为在第 i 子段中, a[j]的值是不断变化的, 总有 dp[k][j]是当前最大值.
- // 还得进一步加深对 dp 的理解.
- }
- }
- ll ans=-INF;
- for(int i=m;i<=n;i++) // 找到第 m 行的最大值, 即为答案
- ans=max(ans,dp[m&1][i]);
- printf("%lld\n",ans);
- }
- }
来源: http://www.bubuko.com/infodetail-2763037.html