題目分析：
由題目很容易就能想到這道題目是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 ;
}
#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 ;
}
