http://poj.org/problem?id=1036

题目分析：

由题目很容易就能想到这道题目是DP题目。

当然，它的DP方程也不难得到：

定义状态：d[i,j] 表示在时间t=i且门状态为j的时候所能取得的最大幸运值。

那么相应的状态转移方程为

d[i,j] =max(d[i-1,j-1],d[i-1,j],d[i-1][j+1])+p

如果在i时刻有坚毅度为j的混混k出现，则p=Sk，否则，p=0

由此可得该题的状态数目为O(T*K)，决策数目为O(1)

总的时间复杂度为O(T*K)，空间复杂度为O(T*K)。

似乎题目到此就能解题成功了，但是并非如此。

可以看到题目中Memory Limit: 10000K，这样的空间来装一个T*K即30000*100的整型数组肯定会超空间，那么该怎么办呢？

聪明的你应该能想到“离散化”（wy的专业术语，在此借用一下）。对，注意到混混的人数为1<=N<=100，T*K这么大的空间根本就没有必要开，我们只需要对混混来的时间排一下序，然后依次编号，就可以把空间减小为N*K。

至此，我们的DP方程稍稍改变一下：

定义状态：d[i,j] 表示在第i号时间且门状态为j的时候所能取得的最大幸运值。

那么相应的状态转移方程为

d[i,j] = max(d[i-1,k])+p，

其中j-interval(i-1,i)<= k <= j+interval(i-1,i)，

interval(i-1,i)表示第i-1号时间到第i号时间的间隙

如果在i时刻有坚毅度为j的混混k出现，则p=Sk，否则，p=0

通过这样的压缩，我们把空间复杂度减为了O(N*K)。

于是这样一道题目就被解决了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<bitset>

#include<iomanip>

using namespace std;

#define MAX 110

#define MAXK 1110

#define MAXT 11110

struct node

{

	int time , pros , stout ;

}a[ MAX ] ;

bool cmp( node a , node b )

{

	return a.time < b.time ;

}

int main()

{

	int dp[ MAX ][ MAXK ] , timetable[ MAX ] ;

	bool get[ MAX ][ MAXK ] ;

	int i,j,count,count0,time_num,time,p,d,res;

	int n , k , t , hh;

	scanf( "%d%d%d" , &n , &k , &t ) ;

	for( int i = 0 ; i < n ; ++i )

		scanf( "%d" , &a[ i ].time ) ;

	for( int i = 0 ; i < n ; ++i )

		scanf( "%d" , &a[ i ].pros ) ;

	for( int i = 0 ; i < n ; ++i )

		scanf( "%d" , &a[ i ].stout ) ;

	sort( a , a + n , cmp ) ;

	memset( get , false , sizeof( get ) ) ;

	timetable[ time_num = 0 ] = 0 ;

	for( i = 0 ; i < n ; ++i )

		if( a[ i ].time  != timetable[ time_num ] )

			timetable[ ++time_num ] = a [ i ].time ;

	get[ 0 ][ 0 ] = true ;

	count = 0 ;

	hh = 0 ;

	while( count < time_num )

	{

		time = timetable[ count ] ;

		while( hh < n && a[ hh ].time == time )

		{

			if( get[ count ][ a[ hh ].stout ] )

				dp[ count ][ a[ hh ].stout ] += a[ hh ].pros ;

			hh++ ;

		}

		count0 = count + 1 ;

		d = timetable[ count0 ] - time ;

		for( j = 0 ; j < k + 1; ++j )

			if( get[ count ][ j ] )

				for( p = max( j - d , 0 ) ; p <= min( j + d , k ) ; ++p )

				{

					if( dp[ count0 ][ p ] < dp[ count ][ j ] )

						dp[ count0 ][ p ] = dp[ count ][ j ] ;

					get[ count0 ][ p ] = true ;

				}

		count ++ ;

	}

	time = timetable[ count ] ;

	for( i = 0 ; i < n && a[ i ].time <= time ; ++i )

		if( a[ i ].time == time )

			if( get[ count ][ a[ i ].stout ] )

				dp[ count ][ a[ i ].stout ] += a[ i ].pros ;

	res = 0 ;

	for( i = 0 ; i < k + 1  ; ++i )

		if( dp[ count ][ i ] > res )

			res = dp[ count ][ i ] ;

	printf( "%d\n" , res ) ;

	return 0 ;

}