HDU 1176 免费馅饼

类似于数塔的变形，只不过是每个数下面要取的是三个数的最大值，另外注意边界。

第0秒 5

第1秒 4 5 6

第2秒 3 4 5 6 7

第3秒 2 3 4 5 6 7 8

第4秒 1 2 3 4 5 6 7 8 9

第5秒 0 1 2 3 4 5 6 7 8 9 10

第6秒 0 1 2 3 4 5 6 7 8 9 10

第7秒 .................

我的代码：

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 int dp[100001][12];
 5 int max1(int a,int b,int c)
 6 {
 7     if(a>=b&&a>=c)
 8         return a;
 9     else if(b>=a&&b>=c)
10         return b;
11     else
12         return c;
13 };
14 int max2(int a,int b)
15 {
16     return a>b?a:b;
17 };
18 
19 int main()
20 {
21     int i,j,n,tt,x,t;
22     while(~scanf("%d",&n)&&n!=0)
23     {
24         tt=0;
25         memset(dp,0,sizeof(dp));
26         while(n--)
27         {
28             scanf("%d%d",&x,&t);
29             dp[t][x]++;
30             if(t>tt)
31                 tt=t;
32         }
33         for(i=tt; i>=1; i--)
34         {
35             dp[i-1][0]+=max2(dp[i][0],dp[i][1]);
36             dp[i-1][10]+=max2(dp[i][9],dp[i][10]);
37             for(j=1; j<=9; j++)
38             {
39                     dp[i-1][j]+=max1(dp[i][j-1],dp[i][j],dp[i][j+1]);
40             }
41         }
42         printf("%d\n",dp[0][5]);
43     }
44 }

网上还有一种做法，是从上往下求解的（代码地址：http://www.clanfei.com/2012/04/646.html）

我刚开始的时候也是从上往下求的，但是没考虑前四秒，即使有些地方馅饼很多game也拿不到，而且我还对时间和位置排了序，后来发现没必要，还是有点和贪心混了…………

网上这种方法是把dp数组和输入的a数组分开的，而dp数组初始为0，所,以不会出现我的这种错误。但是还是用从下往上求比较好。