Codeforces Round 73 D dp

痛定思痛。 2024-04-20 08:36 58阅读 0赞

链接：[http://codeforces.com/contest/1221/problem/D][http_codeforces.com_contest_1221_problem_D]

题意：有一排栅栏，每个栅栏有一个高度和升高一单位所需money，求让相邻两个栅栏高度互不相同的最小花费。

题解：每个栅栏被修改只有三种情况，分别是修改0，修改1，修改2 。然后，背包。

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M=3e5+50;
    #define ll long long
    ll n,m,a[M],b[M],dp[M][3];
    int main(){
        int T;scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
            dp[1][0]=0;
            dp[1][1]=b[1];
            dp[1][2]=b[1]+b[1];
            for(int i=2;i<=n;i++){
                for(int j=0;j<=2;j++){
                    dp[i][j]=1e18;
                    for(int k=0;k<=2;k++){
                        if(a[i]+j!=a[i-1]+k){
                            dp[i][j]=min(dp[i][j],dp[i-1][k]+b[i]*j);
                        }
                    }
                }
            }
            printf("%lld\n",min(dp[n][0],min(dp[n][1],dp[n][2])));
        }
        return 0;
    }

[http_codeforces.com_contest_1221_problem_D]: http://codeforces.com/contest/1221/problem/D

发表评论取消回复

表情：

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

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

相关阅读

相关 Codeforces Round 73 D dp

接：[http://codeforces.com/contest/1221/problem/D][http_codeforces.com_contest_1221_pro...

痛定思痛。/ 2024年04月20日 08:36/ 0 赞/ 59 阅读

相关 Codeforces Round #834 (Div. 3) D. Make It Round

[Problem - D - Codeforces][] ![1c21641e1301413ea5db4b38f928ab5a.png][] Code： incl

￡神魔★判官ぃ/ 2024年03月31日 13:51/ 0 赞/ 83 阅读

相关 Codeforces Round #637 (Div. 2) D. Nastya and Scoreboard 线性DP

题目链接：http://codeforces.com/contest/1341/problem/D 题意：0~9的数字是由图中的木棒组成的，现在给你若干个显示屏，你可以恰

灰太狼/ 2023年05月21日 07:15/ 0 赞/ 22 阅读

相关 Codeforces Round #739 (Div. 3)（编辑距离+数位dp）

a int n; int arr[N]; void solve() { cin >> n; cout <

本是古典何须时尚/ 2022年09月06日 00:21/ 0 赞/ 140 阅读

相关 codeforces 519D dp

D. A and B and Interesting Substrings time limit per test 2 seconds memory limit per

雨点打透心脏的1/2处/ 2022年07月24日 05:08/ 0 赞/ 174 阅读

相关 Codeforces Round #402 (Div. 2) （A-D）

[CF \402 div2][CF _402 div2] A题：数学。具体看代码吧。很容易明白的。 include<bits/stdc++.h> usi

客官°小女子只卖身不卖艺/ 2022年07月12日 15:16/ 0 赞/ 201 阅读

相关 Codeforces Round #397 E. Tree Folding （树形dp）

E. Tree Folding time limit per test 2 seconds memory limit per test 512 megabytes i

Bertha 。/ 2022年07月12日 08:51/ 0 赞/ 211 阅读

相关 Codeforces Beta Round #8 E. Beads （数位dp）

题目链接： [点击打开题目][Link 1] 题意：将所有二进制串（只允许前导 0）中，同时满足字典序不小于其逆序串，取反串和逆序取反串（三种都要满足）的

迷南。/ 2022年06月17日 12:22/ 0 赞/ 159 阅读

相关 CodeForces 189D(最短路+dp)

问题描述: PMP is getting a warrior. He is practicing a lot, but the results are not accepta

我不是女神ヾ/ 2022年06月02日 05:09/ 0 赞/ 164 阅读

相关 Codeforces Round #677 D. Districts Connection

[题目][Link 1] 题意：给出n个点，对n个点连n-1条边要求构成一棵树，其中对于树中属于同一帮派的点不能相互连边。则我们只需对所有的点进行连边尝试，直到连了n-1

迈不过友情╰/ 2021年07月16日 18:57/ 0 赞/ 264 阅读