学步园

一开始，不理解题目意思，都不知道样例是如何计算出来的。

看到discuss中有人说了题目的意思是：有个伸缩门，门的宽度0~K，每个时间可以伸长或缩短1个单位，有N个流氓，他们在T时刻到达，如果这时门的宽度正好与他们的stoutness相等时，便可获得一定的收入，问最大的收入是多少。

看不到题目说什么伸缩门，不知道这是什么翻译，但是总算理解题目意思了，其实就是个背包。就是在第i个流氓能进的时候，让不让他进，因为他会影响到后面价值更大的流氓。

状态方程：

f[i] = max(f[i] , f[j] + gangster.p[i])(表示到第i个流氓时，他不进入就是f[i]，如果他进入，那么（0=<j<i）求最大值加上i的价值)。

注意如果到了时间，但是在这个时间内，门无法达到当前流氓的状态，那么就是0，这也是初始化操作。并且当前流氓进入时间与前一个时间的差值一定要能够满足门状态的变化，否则此流氓永远离开。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define nMax 110
#define Max(a,b) (a>b?a:b)
struct Gangster
{
	int t,p,s;
}gangster[nMax];

int cmp(const void *a, const void *b)
{
	struct Gangster *c = (struct Gangster *)a;
	struct Gangster *d = (struct Gangster *)b;
	return c->t - d->t;
}
int N,K,T,f[nMax];

int main()
{
	while (scanf("%d %d %d", &N, &K, &T) != EOF)
	{
		for (int i = 0; i < N; ++ i)
		{
			scanf("%d", &gangster[i].t);
		}
		for (int i = 0; i < N; ++ i)
		{
			scanf("%d", &gangster[i].p);
		}
		for (int i = 0; i < N; ++ i)
		{
			scanf("%d", &gangster[i].s);
		}
		qsort(gangster, N, sizeof(gangster[0]), cmp);//流氓进入的时间排序
	//	memset(f, 0, sizeof(f));
		for (int i = 0; i < N; ++ i)
		{
			if (gangster[i].t >= gangster[i].s)//如果在时间i时，门能够达到流氓进入的要求，那么就初始化他的价值
			{
				f[i] = gangster[i].p;
			}
			else//否则此流氓离开，永远不会来
			{
				f[i] = -1;
				continue;
			}
			for (int j = 0; j < i; ++ j)//dp求第i个流氓进或者不进的最大价值
			{
				if (abs(gangster[j].s - gangster[i].s) <= abs(gangster[j].t - gangster[i].t))//必须满足前一个流氓到第i个之间的时间差能够满足门的变化
				{
					f[i] = Max(f[i], f[j] + gangster[i].p);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < N; ++ i)//求出最大值即为最大价值
		{
			ans = Max(ans, f[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}