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

【算法分析】

动态规划：线性动规

? ? ? ?该题可以抽象为：将由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;
}