题目大意: 宾馆有个伸缩门,其开放状态用[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<=&& 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