hdu1087Super Jumping! Jumping! Jumping!(dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1087

7A。。。。简单的递推没考虑负数的情况一直乱改。。

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #define INF 0xfffffff
 5 using namespace std;
 6 long long dp[1011],a[1011];
 7 int main()
 8 {
 9     int i,j,k,n,m;
10     while(scanf("%d",&n)&&n)
11     {
12         memset(dp,0,sizeof(dp));
13         for(i = 1; i <= n ; i++)
14         scanf("%lld",&a[i]);
15         dp[0] = 0;
16         long long max = 0;
17         for(i = 1; i <= n; i++)
18         {
19             long long tmax = 0;
20             if(a[i]<=0)
21             {
22                 dp[i] = 0;
23                 continue;
24             }
25             for(j = 0; j <i ; j++)
26             {
27                 if(a[i]>a[j]&&a[j]>=0&&dp[j]+a[i]>tmax)
28                     tmax = dp[j]+a[i];
29             }
30             dp[i] = tmax;
31             if(tmax>max)
32             max = tmax;
33         }
34         printf("%lld\n",max);
35     }
36     return 0;
37 }