我一方面刻苦学习了小岛大牛的思路并且AC了，一方面惊异于这么多人AC也没有个人写点通俗的题解让我们小菜更易懂一点……还是说那个题解已经很好了只不过我看不太懂……

我按照那个思路稍微通俗的写一些吧。、

***|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|*

我觉得这个O(n^2)的算法很值得我学习。

f.(a,b)表示前i个拼图取出j个所需要的最小集合数为a，在这种情况下最后一个集合的最小拼图块数为b（用记录数组）。

我用g[i]表示第i个拼图的拼图块数

两个决策

1、把这块拼图扔了(-_-||)：f.(a,b)。

2、将这块拼图拿进来，但是因为有可能导致非法情况，考虑到之前的决策都是最优的，而我们又一定要这块拼图，所以有：

if f.b+g[i]

中学生来写题解了

#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;
}

来段像样点的题解
//先发代码
#include<bits/stdc++.h>
using namespace std;

int num[1005], f[1005][1005], g[1005];
int n, m, t;

int main()
{
cin>>n>>m>>t;
for(int i=1;i<=n;i++) scanf("%d", &num[i]);
for(int i=1;i<=n;i++)
for(int j=min(m, i);j>=1;j--){
for(int k=t;k>num[i];k--){
f[j][k]=max(f[j][k], f[j][k-num[i]]+1);
g[j]=max(f[j][k], g[j]);
}
f[j][num[i]]=g[j-1]+1;
g[j]=max(g[j], f[j][num[i]]);
}
cout<<g[m]<<endl;
return 0;
}
//再说说思路
//f(i, j, k)代表用前i块拼图块，分成j个拼图，最后一个拼图有k个块
//而i这一维不需要
//就最后一块取或不取，k==num[i]特殊处理（因为这样不取最后一块前面只有j-1个拼图）
//即f(j, k) = max(f(j-1, k), f(j, k-num[i]),注意k==num[i]时f(j, k)=max{f(j-1, x)}
//这里我用g(j)记max{f(j, x)}

（题目大意：从长n序列中弄出m个子序列，子序列的最左最右内的区间不能相交，求最大个数）
O(n2)DP
劲啊 没想出来
可以不用结构体，把图集数乘10000就是了
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#define _M 10000
using namespace std;

int n, m, t, a[1010], d[1010][1010];

inline int cost(int x, int y) {
if(x % _M <= t - y) return x + y;
return (x / _M + 1) * _M + y;
}

inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }

int main() {
int i, j, ans = 0;
freopen("in.txt", "r", stdin);
scanf("%d%d%d", &n, &m, &t);
for(i = 0;i ++ < n;) scanf("%d", a+i);
memset(d, 0x3f, sizeof(d));
d[0][0] = 10000;
for(i = 0;i ++ < n;) {
for(j = 0;j ++ < i;) {
d[i][j] = min(d[i-1][j], cost(d[i-1][j-1], a[i]));
if(d[i][j] <= _M * m + t) ans = max(ans, j);
}
}
cout << ans;
return 0;
}
```

一开始想f[i][j][k]表示i个分j段，最后一段的w为k的最多拼图个数

然后像背包一样转移，不选i或者选i，选的话可能是从本段来的，也可能是刚好新开一段

把i滚动数组掉，维护一个mx[i][j]表示i个分j段段最大值，方便新开一段这个转移

注意f[i][j][0]＝mx[i-1][j-1]

然后竟然做出来了，虽然很慢

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

O(n^2)的方法太妙了~

F前I个拼图选了J个的最少集合

F前I个拼图选了J个，最后一个集合的拼图块数目。

那么类似01背包，第I个可以放或者不放。

如果放的话有两种情况

（1）前面一个集合还放得下就直接加进去

（2）前面一个放不下，就要新建一个集合来放。

for i:=1 to n do

begin

for j:=1 to i do

begin

if f+w[i]

编译通过...

├ 测试数据 01：答案错误...

　├ Hint: lolanv好可爱哦..　├ 标准行输出

　├ 错误行输出

...

按小岛神牛的做就对了

一开始初始化没弄好 WA了2次

第121个通过 哈哈哈

摘自下面小岛：

c:=min{ c,c+a[i] }，其中

c+a[i]=(c.a , c.b+a[i]) (c.b+a[i] T)

最后Ans=max{i | c[n,i] < M}

O(n^2)

---|---|---|--~~~~~~~~~~性感的分割线---|~~~~~~~~---|---|--~~~~~~~~~~~~~~

刚开始看不懂，突然明白

上面的c类型是一个记录

type

node=record

a,b:longint;

end;

c:array[0..1000,0..1000]of node

这点点破就好办了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第111个........哈哈

Accepted 有效得分：100 有效耗时：0ms

f表示前i个拼图 取j个的‘最少时间’

f:=min(f,sum(f,c[i]))

想了个n*m*t的dp很高兴地过了样例

交上去后超时得很爽- -。

楼上小岛大牛的那个状态表达方式好厉害- -..

自己想了半天不会实现成代码

求参考代码..

少了一个=

太晕了!

实在没有后效性

这个DP让我觉得有点诡异……感觉里面有贪心的思想……

已修改|

管理员看一下...描述怎么空了...

贴一段比赛那天发的solution...

拼拼图的小杉

描述

歹徒告诉小杉，他正在寻找的拼图块其实可以拼成N个 有顺序的 完整的拼图。

每个完整的拼图由若干个拼图块组成。

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

小杉要找出划分成M个集合后，M个集合中最多能有多少个完整的拼图。

每组测试数据的

第一行有三个，为N,M,T(1

此题和usaco 3.4.4 rockers描述完全一样，只是数据范围扩大了。

用O(n2)的DP过。

Free_Show真乃大牛也，写出那样优美的方程，不愧是青年才俊，国家栋梁，祖国的明天啊！

我来看看……

小杉拼拼图..