本文主要是介绍VIJOS1392拼拼图的小杉，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意
给定n个数，将这n个数中的一些依次放进m个集合，每个集合中所有数的和不能超过T。集合包含的元素不能交叉，也就是说如果第1个数和第3个数放入了集合1，那么第2个数要么放入集合1，要么不放入任何一个集合。
求m个集合中最多能包含多少个数
1<=n,m,T<=1000
分析
来源于题解中小岛的想法
这题如果状态直接定义为f[i,j]=x表示前i个数放入j个集合最多能包含x个数
那么操作起来会比较困难，所有应换一种状态的定义。
记a[i]为第i个数，f[i,j]=(t,s)表示前i个数选了j个数需要t个集合，最后一个集合所有数之和为s，那么
f[i,j]=min{f[i-1,j],f[i-1,j-1]+a[i]}
f[0,0]=(1,0)
那么就是一个0-1背包问题啦
最后的答案是使得f[n,i]的t<=m的最大的i
代码
#include<cstdio>
const int maxn=1000;
int n,m,T,a[maxn+10];
struct node{int t,s;bool operator < (const node d) const{if (t<d.t)return 1;if (t>d.t)return 0;return s<d.s;}node operator + (const int d) const{if (s+d<=T)return (node){t,s+d};elsereturn (node){t+1,d};}
};
node f[maxn+10];
int main(){scanf("%d%d%d",&n,&m,&T);node te;for (int i=1;i<=n;i++)scanf("%d",&a[i]);f[0].t=1;for (int i=1;i<=n;i++){f[i]=f[i-1]+a[i];for (int j=i-1;j>=1;j--){te=f[j-1]+a[i];if (te<f[j])f[j]=te;}}for (int i=n;i>=0;i--)if (f[i].t<=m){printf("%d\n",i);return 0;}
}这篇关于VIJOS1392拼拼图的小杉的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
