1278:【例9.22】复制书稿(book)

2023-12-18 20:36:16

【算法分析】

动态规划:线性动规

? ? ? ?该题可以抽象为:将由m个数字构成的序列分成k个子段。对于每种子段分割方案,都能求出所有子段中的最大子段和。求所有方案中最大子段和最小的分割子段的方案。

1. 状态定义
集合:子段分割方案
限制:看前几个数字,分成几个子段
属性:最大子段和
条件:最小
统计量:最大子段和
状态定义:dp[i][j]:将前i个数字分成j个子段的方案中最大子段和最小的方案的最大子段和。
初始状态:dp[i][1]:前i个数字分成1段,就是前i个数字的和。

2. 状态转移方程
记数组a的前缀和数组为s,a[i]~a[j]的子段和为s[j]-s[i-1]
集合:将前i个数字分成j个子段的方案
分割集合:根据第j子段的元素个数来分割集合

如果第j子段只有a[i],那么将前i个数字分成j个子段的最大子段和最小的方案的最大子段和,为将前i-1个数字分成j-1个子段的最大子段和最小的方案的最大子段和,再与第j子段比较得到的最大子段和。dp[i][j] = max(dp[i-1][j-1], a[i])
如果第j子段有a[i-1]a[i],那么将前i个数字分成j个子段的最大子段和最小的方案的最大子段和,为将前i-2个数字分成j-1个子段的最大子段和最小的方案的最大子段和,再与第j子段比较得到的最大子段和。dp[i][j] = max(dp[i-2][j-1], a[i]+a[i-1])

如果第j子段为a[j]~a[i]。那么将前i个数字分成j个子段的最大子段和最小的方案的最大子段和,为将前j-1个数字分成j-1个子段的最大子段和最小的方案的最大子段和,再与第j子段的子段和s[i]-s[j-1]比较得到的最大子段和。dp[i][j] = max(dp[j-1][j-1], s[i]-s[j-1])
综上,h从j开始增加到i(h最小时前h-1个数字与子段数j-1相等,有h = j ),取第j子段为a[h]~a[i],有dp[i][j] = max(dp[h-1][j-1], s[i]-s[h-1]))。
以上所有情况取最小值。
?

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define N 505
int m, k, a[N], s[N];//a:数字序列 s:前缀和
int dp[N][N];//dp[i][j]:将前i个数字分成j个子段的方案中最大子段和最小的方案的最大子段和。
void show(int i, int x)//输出数组a[1]~a[i]中子段和小于等于x的所有子段左右端点(子段长度从小到大) 
{
    if(i == 0)
        return;
    int j, sum = 0;
    for(j = i; j >= 1 && sum+a[j] <= x; --j)
        sum += a[j];
    show(j, x);//输出a[1]~a[j]中的子段 
    cout << j+1 << ' ' << i << endl;  
}
int main()
{
    cin >> m >> k;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    memset(dp, 0x3f, sizeof(dp));//dp初始化为无穷大 
    for(int i = 1; i <= m; ++i)//前i个数字分成1段,就是前i个数字的和
        dp[i][1] = s[i];
    for(int i = 1; i <= m; ++i)
        for(int j = 2; j <= k; ++j)
            for(int h = j; h <= i; ++h)//取子段a[h]~a[i] 
                dp[i][j] = min(dp[i][j], max(dp[h-1][j-1], s[i]-s[h-1]));
    show(m, dp[m][k]); 
    return 0;
}

文章来源:https://blog.csdn.net/pheatonhb/article/details/135066281
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。