题目大意： 宾馆有个伸缩门，其开放状态用[0,k]之间某个数来表示，每秒钟它至多可以伸长或减少1个单位。现在有n个强盗，他们会在ti的时间到达宾馆，如果此时门的开放度和他的身材si恰好相同，他就会进来，并得到pi的加分。一开始门是关闭的(开放度为0)，请你求出时刻t的最大加分。


解题思路：1）这道题的状态很容易就可以找出来：dp[i][j]表示在第i秒钟门的宽度为j所取得的最大加分。
              2）那么转移就是：dp[i][j]=Max{dp[i-1][j+1],dp[i-1][j-1],dp[i][j]}+dp[i][j]~前一个时刻可以由三个状态转变而来，直接求最大值就可以了
              3) 这道题的空间限制是10000K~，完整的数组开不了，只能开滚动数组~（WA了之后才发现的）

~~本以为改为滚动数组后就过了~~，没想到果断T了~~，没办法，又加了张hash记录强盗在什么时刻到达宾馆来稍微稍微降低复杂度。


代码：
 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4#include <string>
 5#include <cmath>
 6#include <algorithm>
 7
 8using namespace std;
 9
10struct Person
11{
12    int t,s,p;
13}num[110];
14int dp[3][110];
15int hash[30100];
16int n,t,k,summ;
17
18
19void init()
20{
21    memset(dp,0,sizeof(dp));
22    memset(hash,0,sizeof(hash));
23}
24
25void get_DP()
26{
27    for (int i=0; i<=t; i++)
28    {
29        for (int j=0; j<=k && j<=i; j++)
30        {
31            summ=0;
32            if (hash[i]!=0)
33            {
34                for (int l=0; l<n; l++)
35                    if (i==num[l].t && j==num[l].s) summ+=num[l].p;
36            }
37            if (j==k) dp[i%3][j]=max(dp[(i+2)%3][j-1],dp[(i+2)%3][j]);
38            else if (j==0) dp[i%3][j]=max(dp[(i+2)%3][j+1],dp[(i+2)%3][j]);
39            else dp[i%3][j]=max(max(dp[(i+2)%3][j-1],dp[(i+2)%3][j]),dp[(i+2)%3][j+1]);
40            dp[i%3][j]+=summ;
41        }
42    }
43}
44
45int cmp(const Person &a,const Person &b)
46{
47    if (a.t==b.t) return a.s<b.s; else return a.t<b.t;
48}
49
50int main()
51{
52    scanf("%d%d%d",&n,&k,&t);
53
54    for (int i=0; i<n; i++)
55        scanf("%d",&(num[i].t));
56    for (int i=0; i<n; i++)
57        scanf("%d",&(num[i].p));
58    for (int i=0; i<n; i++)
59        scanf("%d",&(num[i].s));
60    sort(num,num+n,cmp);
61    init();
62    for (int i=0; i<n; i++)
63        hash[num[i].t]=1;
64    get_DP();
65    int maxx=-1;
66    for (int i=0; i<=k; i++)
67        if (maxx<dp[t%3][i])  maxx=dp[t%3][i];
68    printf("%d",maxx);
69    return 0;
70}
71