[已解决]登山（还是关于dp的题目）

bangbang-ande

网址：http://ybt.ssoier.cn:8088/problem_show.php?pid=1283

这题虽然代码写了出来，但运行了好几次都不对，这又是如何回事呢？
大神指教
代码（便于复制）:

1. #include <stdio.h>
   
2. 
   
3. int main(void){

复制代码

大家加油，我无能为力了

最佳答案

月排行榜 / 总排行榜

baige

2021-3-9 22:57:13

1. #include <stdio.h>
   
2. #define max(a, b) (a > b ? a : b)
   
3. 
   
4. int a[1010], dp[1010][2];
   
5. int n;
   
6. 
   
7. int main(void) {
   
8.         scanf("%d",&n);
   
9.         for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
   
10.         for(int i = 0; i < 1010; i++){
    
11.                 dp[i][0] = dp[i][1] = 1;
    
12.         }
    
13.        
    
14.         for(int i = 2; i <= n; i++){
    
15.                 for(int j = i-1; j >= 1; j--){
    
16.                         if(a[j] < a[i]) dp[i][0] = max(dp[i][0], dp[j][0]+1);
    
17.                 }
    
18.         }
    
19.        
    
20.         for(int i = n-1; i >= 1; i--){
    
21.                 for(int j = i+1; j <= n; j++){
    
22.                         if(a[i] > a[j]) dp[i][1] = max(dp[i][1], dp[j][1]+1);
    
23.                 }
    
24.         }
    
25. // 如有疑问，请取消注释看输出
    
26. // 第一个循环表示从1到i的过程中上山的最大观看景点数
    
27. // 第二个循环表示从i到n的过程中下山的最大观看景点数
    
28. // i这个景点重复计算因此需要dp[i][0]+dp[i][1]-1       
    
29. //        for(int i = 1; i <= n; i++){
    
30. //                printf("%d ",dp[i][0]);
    
31. //        }
    
32. //        puts("");
    
33. //        for(int i = 1; i <= n; i++){
    
34. //                printf("%d ",dp[i][1]);
    
35. //        }
    
36. //        puts("");
    
37.        
    
38.         int ans = 0;
    
39.         for(int i = 1; i <= n; i++){
    
40.                 ans = max(ans, dp[i][0]+dp[i][1]-1);
    
41.         }
    
42.         printf("%d\n",ans);
    
43.         return 0;
    
44. }

复制代码

跳转到最佳答案楼层

baige

1. #include <stdio.h>
   
2. #define max(a, b) (a > b ? a : b)
   
3. 
   
4. int a[1010], dp[1010][2];
   
5. int n;
   
6. 
   
7. int main(void) {
   
8.         scanf("%d",&n);
   
9.         for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
   
10.         for(int i = 0; i < 1010; i++){
    
11.                 dp[i][0] = dp[i][1] = 1;
    
12.         }
    
13.        
    
14.         for(int i = 2; i <= n; i++){
    
15.                 for(int j = i-1; j >= 1; j--){
    
16.                         if(a[j] < a[i]) dp[i][0] = max(dp[i][0], dp[j][0]+1);
    
17.                 }
    
18.         }
    
19.        
    
20.         for(int i = n-1; i >= 1; i--){
    
21.                 for(int j = i+1; j <= n; j++){
    
22.                         if(a[i] > a[j]) dp[i][1] = max(dp[i][1], dp[j][1]+1);
    
23.                 }
    
24.         }
    
25. // 如有疑问，请取消注释看输出
    
26. // 第一个循环表示从1到i的过程中上山的最大观看景点数
    
27. // 第二个循环表示从i到n的过程中下山的最大观看景点数
    
28. // i这个景点重复计算因此需要dp[i][0]+dp[i][1]-1       
    
29. //        for(int i = 1; i <= n; i++){
    
30. //                printf("%d ",dp[i][0]);
    
31. //        }
    
32. //        puts("");
    
33. //        for(int i = 1; i <= n; i++){
    
34. //                printf("%d ",dp[i][1]);
    
35. //        }
    
36. //        puts("");
    
37.        
    
38.         int ans = 0;
    
39.         for(int i = 1; i <= n; i++){
    
40.                 ans = max(ans, dp[i][0]+dp[i][1]-1);
    
41.         }
    
42.         printf("%d\n",ans);
    
43.         return 0;
    
44. }

复制代码

巴巴鲁

我的思路是先排序，再遍历数组
后面比前面大次数+1，相等结束遍历

bangbang-ande

巴巴鲁 发表于 2021-3-10 09:57
我的思路是先排序，再遍历数组
后面比前面大次数+1，相等结束遍历

这种方法好像不行，会超时（时间5s）