线性dp——cf1012C好题

骑猪看日落 2021-12-01 16:46 256阅读 0赞

比较套路的dp题

/*
    dp[i][j][0|1]:前i座山盖了j座房子，第i座不盖|盖 
    dp[i][j][0]=min( dp[i-1][j][0] , 
                     dp[i-1][j][1]+max(0,a[i]-a[i-1]+1) );
    dp[i][j][1]=min( dp[i-2][j-1][0]+max(0,a[i-1]-a[i]+1), 
                     dp[i-2][j-1][1]+max(0,a[i-1]-min(a[i-2],a[i])+1)  );
    因为有冗余态，所以要初始化dp数组 
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    #define maxn 5005
    
    int dp[maxn][maxn][2],n,a[maxn];
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0x3f,sizeof dp);
        dp[0][0][0]=dp[1][1][1]=dp[1][0][0]=0; 
        a[0]=0x3f3f3f3f;
        for(int i=2;i<=n;i++){
            dp[i][0][0]=dp[i-1][0][0];
            for(int j=1;j<=(i+1)/2;j++){
                dp[i][j][0]=min(dp[i-1][j][0],
                                dp[i-1][j][1]+max(0,a[i]-a[i-1]+1));
                dp[i][j][1]=min(dp[i-2][j-1][0]+max(0,a[i-1]-a[i]+1),
                                dp[i-2][j-1][1]+max(0,a[i-1]-min(a[i-2],a[i])+1));
            }
        }
        for(int i=1;i<=(1+n)/2;i++)
            cout<<min(dp[n][i][0],dp[n][i][1])<<'\n';
    }

转载于:https://www.cnblogs.com/zsben991126/p/10953936.html

发表评论取消回复

表情：

评论列表（有 0 条评论，256人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1012

致题意：有k个坏人k个好人坐成一圈，前k个为好人(编号1~k),后k个为坏人(编号k+1 ~ 2k) 现在有一个报数m，从编号为1的人开始报数，报到m的人就要自动死...

深碍√TFBOYSˉ_/ 2024年04月17日 05:25/ 0 赞/ 87 阅读

相关 C/C++之（五）洛谷刷题基础题 --- 新年好

学习之路，长路漫漫，写学习笔记的过程就是把知识讲给自己听的过程。 > 唯有热爱，可抵岁月漫长，唯有热爱，不畏世间无常！ -------------------- ![

红太狼/ 2023年10月04日 20:28/ 0 赞/ 10 阅读

相关【好题】好题分享

> ![e6584f1dfebb4fa3ac10c056b1b418d9.png][] > [1001-四舍五入\_牛客竞赛语法入门班数组模拟、枚举、贪心习题 (nowcod

比眉伴天荒/ 2023年09月24日 17:58/ 0 赞/ 64 阅读

相关 1012: 译码

Description 要将"China"译成密码，译码规律是：用原来字母后面的第4个字母代替原来的字母．例如，字母"A"后面第4个字母是"E"．"E"代替"A"。因此，

╰半橙微兮°/ 2023年01月10日 05:24/ 0 赞/ 180 阅读

相关 Ladygod UESTC - 1012

Ladygod UESTC - 1012 -------------------- Problem 有一天人诹Lee在随手帮女神做题，突然女神发现了自己演算纸上的

深藏阁楼爱情的钟/ 2022年06月14日 10:38/ 0 赞/ 158 阅读

相关杭电1012

u Calculate e Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K

红太狼/ 2022年06月05日 11:56/ 0 赞/ 148 阅读

相关 1012 数字分类

题目描述给定一系列正整数，请按要求对数字进行分类，并输出以下 5 个数字： A1 = 能被 5 整除的数字中所有偶数的和； A2 = 将被 5 除后

谁借莪１个温暖的怀抱￠/ 2022年04月17日 03:49/ 0 赞/ 239 阅读

相关 HDOJ 1012

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 水题天天有，今天特别多....嘿嘿 u Calc

约定不等于承诺〃/ 2022年01月15日 01:37/ 0 赞/ 263 阅读

相关线性dp——cf1012C好题

比较套路的dp题 / dp[i][j][0|1]:前i座山盖了j座房子，第i座不盖|盖 dp[i][j][0]=min( dp[i-1][j][0]

骑猪看日落/ 2021年12月01日 16:46/ 0 赞/ 257 阅读

相关 pat 乙级 1012 数字分类（C语言实现）

给定一系列正整数，请按要求对数字进行分类，并输出以下 5 个数字： A1 = 能被 5 整除的数字中所有偶数的和； A2 = 将被 5 除后余 1 的数字按给出

爱被打了一巴掌/ 2021年09月30日 23:50/ 0 赞/ 348 阅读