原题链接

考察:线性dp

思路:

        乍一看我还以为是背包dp,实际不是,f[i][j]表示第i秒,j位置能得到的最大数.f[i][j] = max(f[i-1][j],f[i-1][j-1],f[i-1][j+1])+w[i][j].每个位置能获得的馅饼数要用另一个数组存,不能用f数组.

        关于如何初始化,除了f[0][5]全部负无穷.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 100010;
 6 int f[N][15],n,w[N][15];
 7 int main() 
 8 {
 9     while(scanf("%d",&n)!=EOF&&n)
10     {
11         int ti = 0;
12         memset(f,-0x3f,sizeof f);
13         memset(w,0,sizeof w);
14         f[0][5] = 0;
15         for(int i=1;i<=n;i++)
16         {
17             int x,ts;
18             scanf("%d%d",&x,&ts);
19             w[ts][x] += 1;
20             ti = max(ti,ts);
21         }
22         for(int i=1;i<=ti;i++)
23           for(int j=0;j<=10;j++)
24           {
25               f[i][j] = max(f[i-1][j]+w[i][j],f[i][j]);
26               if(j-1>=0) 
27                f[i][j] = max(f[i-1][j-1]+w[i][j],f[i][j]);
28               if(j+1<=10) 
29                f[i][j] = max(f[i-1][j+1]+w[i][j],f[i][j]);
30           }
31         int ans = 0;
32         for(int i=0;i<=10;i++) ans = max(f[ti][i],ans);
33         printf("%d\n",ans);
34     }
35     return 0;
36 }