论坛 › C\C++交流 › 登山（还是关于dp的题目）

bangbang-ande 发表于 2021-3-9 22:57:12

登山（还是关于dp的题目）

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

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

int main(void){
大家加油，我无能为力了

baige 发表于 2021-3-9 22:57:13

本帖最后由 baige 于 2021-3-10 21:26 编辑

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

int a, dp;
int n;

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

巴巴鲁 发表于 2021-3-10 09:57:49

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

bangbang-ande 发表于 2021-3-10 22:37:48

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

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

查看完整版本: 登山（还是关于dp的题目）