用last记录上一个进入的人

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct
{
	int time;
	int prosperity;
	int stoutness;
} Gangster;

Gangster gangsters[150];
int val[150];//val[i]为前i个人进入时可获得的最大收益,val[i] = max{ val[k] + (ok() ? p[i] : 0) }ok()判断第i个人是否可以进入
int last[150];//last[i]为前i个人中最后一个进入的人

bool myCompare(const Gangster &g1, const Gangster &g2)
{
	return g1.time < g2.time;
}


int main()
{
	int N, K, T;
	while (cin >> N >> K >> T)
	{
		gangsters[0].time = 0;
		gangsters[0].prosperity = 0;
		gangsters[0].stoutness = 0;

		for (int i = 1; i <= N; ++i)
			cin >> gangsters[i].time;
		for (int i = 1; i <= N; ++i)
			cin >> gangsters[i].prosperity;
		for (int i = 1; i <= N; ++i)
			cin >> gangsters[i].stoutness;

		sort(gangsters + 1, gangsters + 1 + N, myCompare);//按时间排序!!!注意排序范围

		for (int i = 0; i <= N; ++i)
		{
			val[i] = 0;
			last[i] = 0;
		}
		for (int i = 1; i <= N; ++i)
			for (int j = 0; j < i; ++j)
			{
				int tmp = val[j];
				bool in = false;//第i个人是否进入
				if (gangsters[i].time <= T && gangsters[i].stoutness <= K && gangsters[i].prosperity != 0)//满足时间和大门条件!!!且收益不为零
				{
					if ((gangsters[i].time - gangsters[last[j]].time) >= abs(gangsters[i].stoutness - gangsters[last[j]].stoutness))//第i个人可以进入
					{
						tmp += gangsters[i].prosperity;
						in = true;
					}
				}
				if (tmp > val[i])
				{
					val[i] = tmp;
					last[i] = in ? i : j;
				}
			}

		cout << val[N] << endl;
	}

	return 0;
}