「czy系列赛」蒟蒻czy又被D飞了

2014年7月19日3,5863

（本题中的图片忽略）

「题目描述」

机房里的各路巨神天天D蒟蒻CZY，早已是他们的日常任务了。（今天的机房也是很和平呢）

这一次他们安排好了一种方式来D蒟蒻Czy。每个人每次都能把Czy D飞一个高度（让Czy的高度+a[i]），由于他们的精♂力有限（尤其是某些后宫王），要保留体力应对接下来的战♂斗，所以他们每个人只会D Czy k[i]次。由于他们每个人的D人能力不同，各有所长，所以他们每个人都在Czy到一定高度h[i]以后良心发现，任由Czy自生自灭，回去玩达尔文进化岛了。(神犇们：计划通

所以Czy想知道他的速度是否能达到第二宇宙速度，离开这个可怕的地方。但是Czy太弱了，所以这个问题就交给了未来集训队的你。但是你这么吊，哪里屑解答Czy蒟蒻的问题。于是你打算只告诉他最高会飞到什么高度，让他自己算自己的速度去。（蒟蒻无人权

「输入格式」 fly.in

第1行：1个整数N（1<=N<=100）N表示机房里有多少人今天要D 蒟蒻Czy

接下里N行，每行描述一个神犇的信息 a[i] h[i] k[i]

「输出格式」 fly.out

第1行：1个整数H，表示Czy最高会被神犇们D到哪里去

「样例输入」

8 35 1

5 35 1

15 35 1

8 35 1

10 35 1

4 35 1

2 35 1

「样例输出」

数据范围

对于40%的数据所有人的k[i]==1, n<=10,h[i]<=100 且所有人的h[i]相等（天地良心，不要不信

对于100%的数据 1<=k[i]<=30，1<=h[i]<=10000, 1<=a[i]<=200

不做这题的下场如下

题解

本题将每个人拆成30个似乎就行了。。。

但是其实是个有限制的完全背包，看代码吧。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans;bool f[40001];
int use[40001];
struct data{int h,a,c;}a[401];
inline bool cmp(data a,data b)
{return a.a<b.a;}
int main()
{
    //freopen("fly.in","r",stdin);
    //freopen("fly.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c);
    sort(a+1,a+1+n,cmp);
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
		memset(use,0,sizeof(use));
		for(int j=a[i].h;j<=a[i].a;j++)
		{
			if(!f[j]&&f[j-a[i].h]&&use[j-a[i].h]+1<=a[i].c)
			{
				f[j]=1;
				use[j]=use[j-a[i].h]+1;
				ans=max(j,ans);
			}
		}
    }
    printf("%d",ans);
    return 0;
}