hdu1176

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1176

每次决策三种情况取其最大（边界和初始状态特殊处理）。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=100010;
 6 int dp[12][maxn];
 7 int n;
 8 int x,t;
 9 int main()
10 {
11     while(scanf("%d",&n)&&n)
12     {
13         int mt=0;
14         memset(dp,0,sizeof(dp));
15         for(int i=1;i<=n;i++){
16             scanf("%d%d",&x,&t);
17              mt=max(mt,t);   //求出时间最大值
18             dp[x][t]++;
19         }
20         int ans=max(max(dp[4][1],dp[5][1]),dp[6][1]);    //初始状态（第一秒）
21         for(int i=2;i<=mt;i++)
22             for(int j=0;j<11;j++)
23         {
24             if(j==0) dp[j][i]=max(dp[j][i-1],dp[j+1][i-1])+dp[j][i];
25             else if(j==10) dp[j][i]=max(dp[j][i-1],dp[j-1][i-1])+dp[j][i];
26             else dp[j][i]=max(max(dp[j][i-1],dp[j-1][i-1]),dp[j+1][i-1])+dp[j][i];
27             ans=max(ans,dp[j][i]);
28         }
29         printf("%d
",ans);
30 
31     }
32 }