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

bangbang-ande

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

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

#include <stdio.h>

int main(void){

大家加油，我无能为力了

最佳答案

月排行榜 / 总排行榜

baige

2021-3-9 22:57:13

#include <stdio.h>
#define max(a, b) (a > b ? a : b)

int a[1010], dp[1010][2];
int n;

int main(void) {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        for(int i = 0; i < 1010; i++){
                dp[i][0] = dp[i][1] = 1;
        }
        
        for(int i = 2; i <= n; i++){
                for(int j = i-1; j >= 1; j--){
                        if(a[j] < a[i]) dp[i][0] = max(dp[i][0], dp[j][0]+1);
                }
        }
        
        for(int i = n-1; i >= 1; i--){
                for(int j = i+1; j <= n; j++){
                        if(a[i] > a[j]) dp[i][1] = max(dp[i][1], dp[j][1]+1);
                }
        }
// 如有疑问，请取消注释看输出
// 第一个循环表示从1到i的过程中上山的最大观看景点数
// 第二个循环表示从i到n的过程中下山的最大观看景点数
// i这个景点重复计算因此需要dp[i][0]+dp[i][1]-1        
//        for(int i = 1; i <= n; i++){
//                printf("%d ",dp[i][0]);
//        }
//        puts("");
//        for(int i = 1; i <= n; i++){
//                printf("%d ",dp[i][1]);
//        }
//        puts("");
        
        int ans = 0;
        for(int i = 1; i <= n; i++){
                ans = max(ans, dp[i][0]+dp[i][1]-1);
        }
        printf("%d\n",ans);
        return 0;
} 

跳转到最佳答案楼层

baige

#include <stdio.h>
#define max(a, b) (a > b ? a : b)

int a[1010], dp[1010][2];
int n;

int main(void) {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        for(int i = 0; i < 1010; i++){
                dp[i][0] = dp[i][1] = 1;
        }
        
        for(int i = 2; i <= n; i++){
                for(int j = i-1; j >= 1; j--){
                        if(a[j] < a[i]) dp[i][0] = max(dp[i][0], dp[j][0]+1);
                }
        }
        
        for(int i = n-1; i >= 1; i--){
                for(int j = i+1; j <= n; j++){
                        if(a[i] > a[j]) dp[i][1] = max(dp[i][1], dp[j][1]+1);
                }
        }
// 如有疑问，请取消注释看输出
// 第一个循环表示从1到i的过程中上山的最大观看景点数
// 第二个循环表示从i到n的过程中下山的最大观看景点数
// i这个景点重复计算因此需要dp[i][0]+dp[i][1]-1        
//        for(int i = 1; i <= n; i++){
//                printf("%d ",dp[i][0]);
//        }
//        puts("");
//        for(int i = 1; i <= n; i++){
//                printf("%d ",dp[i][1]);
//        }
//        puts("");
        
        int ans = 0;
        for(int i = 1; i <= n; i++){
                ans = max(ans, dp[i][0]+dp[i][1]-1);
        }
        printf("%d\n",ans);
        return 0;
} 

巴巴鲁

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

bangbang-ande

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

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