题目链接:https://vijos.org/p/1392

题目背景

小杉的幻想来到了经典日剧《死亡拼图》的场景里……
被歹徒威胁，他正在寻找拼图（-.-干嘛幻想这么郁闷的场景……）。
突然广播又响了起来，歹徒竟然又有了新的指示。
小杉身为新一代的汤浅，有责任带领大家脱离危险！
（若对情节有任何疑问，请观看原剧）

题目描述

歹徒告诉小杉，他正在寻找的拼图块其实可以拼成N个 有顺序的 完整的拼图。
每个完整的拼图由若干个拼图块组成。
歹徒要求小杉把拼图按拼出的顺序划分成M个集合，一个拼图集合由若干个完整的拼图组成，并且总的拼图块的数目不超过T。并且，构成集合的拼图是不能交叉的，例如，当拼图1与拼图3被放在拼图集合1中之后，拼图2就只能放进拼图集合1或者不放进任何拼图集合。
小杉要找出划分成M个集合后，M个集合中最多能有多少个完整的拼图。

输入格式

每组测试数据的
第一行有三个，为N,M,T(1<=N,M,T<=1000)
第二行有N个数，按照拼出拼图的顺序给出N个拼图分别含有多少个拼图块（拼图块的个数是不超过T的正整数，并且你不必考虑在现实中是否真正存在该个数的拼图）。

特别地，对于30%的数据，有1<=N,M<=100

输出格式

对每组数据输出一行一个数字，为M个拼图集合最多包含的拼图个数

样例输入

6 2 4
1 1 3 1 2 2

样例输出

5

限制

每个测试点1s.

提示

对于样例数据，1个可行的方案如下:
拼图集合1放拼图1,2和拼图4,
拼图集合2放拼图5和拼图6,
于是包含5个拼图,
并且显然不存在能够放5个以上拼图的方案.

题意

给定n个数，将这n个数中的一些依次放进m个集合，每个集合中所有数的和不能超过T。集合包含的元素不能交叉，也就是说如果第1个数和第3个数放入了集合1，那么第2个数要么放入集合1，要么不放入任何一个集合。 
求m个集合中最多能包含多少个数。

解题思路

一开始想f[j][k]表示分j段不超过k，然后像背包一样转移，不选i或者选i，选的话可能是从本段来的，也可能是刚好新开一段。
dp[i][j]表示i个分j段段最大值，方便新开一段这个转移。
f[j][0]＝dp[i-1][j-1]。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1005;
int n, m, t, w[N], f[N][N], dp[N][N];
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            f[j][0] = dp[i - 1][j - 1];
            for (int k = t; k > 0; k--) {
                if (k - w[i] >= 0)
                    f[j][k] = max(f[j][k], f[j][k - w[i]] + 1);
                dp[i][j] = max(dp[i][j], f[j][k]);
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}