洛谷解题报告

1.题面

2.分析

好吧，一道标准动归

什么是动归(请大佬跳过以下内容，翻到下一个引用条)

emmmmm好吧，动归(dp)的全称是动态规划，它的主要思路是把一个大问题分成若干个子问题解决。不过，这些分解出来的子问题有时候会有重复的，所以就需要动态规划数组来存储数据。动态规划的特征包括：无后效性和最优子结构。“无后效性”是说以后的选择不会影响以前的选择。“最优子结构”是指如果要让这个问题最优的话，那这个问题繁衍出来的子问题也必须是最优的。

真正的思路分析

嗯，这道题的状态f[i][j]表示的是前i个人抄前j本书的“最大页数”的最小值。
然后就是状态转移方程。算第i个人时，我们可以先看前i — 1个人抄啥书，再把剩下的一起推给第i个人。
也就是说:f[i][j] = min{max(f[i - 1][k], sum[k + 1][j])}(好绕啊) 其中，k的取值范围是1~j。

3.代码

//
//  main.cpp
//  c++programs
//
//  Created by Theodore H on 2019/5/15.
//  Copyright © 2019 Theodore H. All rights reserved.
//

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <time.h>
#include <climits>
#include <deque>
//以上废话
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int n, m;//n是几本书, m是几个人
int sum[505];//前缀和
int f[505][505];//dp数组
int tag[505][505];//tag[i][j]表示前i - 1个人抄了几本书。
int ans[505][2];//答案

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int page;
        cin >> page;
        sum[i] = sum[i - 1] + page;//前缀和(不懂看yxc老师的视频)
    }
    for(int i = 1; i <= n; i++)//从这
    {
        f[1][i] = sum[i];
        tag[1][i] = 0;
    }//到这 是初始化
    for(int i = 2; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = 1 << 30;//1 << 30 是1073741824
            for(int k = 0; k <= j; k++)//从这
            {
                int ict = sum[j] - sum[k];
                int ct = max(f[i - 1][k] , ict);
                if(ct < f[i][j])
                {
                    f[i][j] = ct;
                    tag[i][j] = k;
                }
            }//到这 是枚举k
        }
    }
    //从这
    int tmp = n;
    for(int i = m; i > 0; i--)
    {
        ans[i][0] = tag[i][tmp] + 1;
        ans[i][1] = tmp;
        tmp = tag[i][tmp];
    }//到这 是处理答案
    for(int i = 1; i <= m; i++)//从这
    {
        cout << ans[i][0] << ' ' << ans[i][1] << endl;
    }//到这是输出
    return 0;
}

至此，我的题解解题报告写完了。