首页 > 其他分享 >atcoder 官方dp题单题解(持续更新)

atcoder 官方dp题单题解(持续更新)

时间:2024-06-11 20:10:44浏览次数:11  
标签:atcoder int 题解 cin https tie dp

题单链接:https://atcoder.jp/contests/dp/tasks
洛谷搜索:https://www.luogu.com.cn/problem/list?keyword=at_dp&type=AT|B|CF|P|SP|UVA&page=1

A
题目链接:https://atcoder.jp/contests/dp/tasks/dp_a
简单线性dp. dp[i]表示在i这个位置的最小代价,转移的时候把两种选择都考虑进去就可以了.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int> a(n+1),dp(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[2]=abs(a[1]-a[2]);
    for(int i=3;i<=n;i++)
    { 
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n]<<'\n';

}

B
题目链接:https://atcoder.jp/contests/dp/tasks/dp_b
实际上这题数据范围比较小, \(O(nk)\) 的暴力做法也能过去

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),dp(n+1,1e9);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=max(1,i-k);j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
        }
    }
    cout<<dp[n]<<'\n';
}

标签:atcoder,int,题解,cin,https,tie,dp
From: https://www.cnblogs.com/captainfly/p/18242646

相关文章

  • 题解:P5786 [CQOI2008] 传感器网络
    题意从一个\(n\)个结点的有向无环图里选出\(n-1\)条边,构成一棵树,且除根节点以外的点的儿子个数的最大值最小。输出满足题意的节点的父亲,要求字典序最小。思路我们肯定要先把最小值求出来。很容易看出是拆点+二分答案求解,这里要注意的是拆完的两个点是不用连起来的,将......
  • 用于每个平台的最佳WordPress LMS主题
    你已选择在WordPress上构建学习管理系统(LMS)了。恭喜!你甚至可能已经选择了要使用的LMS插件,这已经是成功的一半了。现在是时候弄清楚哪个WordPressLMS主题要与你的插件配对。我将解释LMS主题和插件之间的区别,以便你了解要寻找什么。然后,我将提供市场上每个最流行......
  • 2024年新高考2卷精选试题解答
    **(2024年新高考2卷19题)**已知双曲线$C:x^2-y^2=m\(m>0)$,点$P_1(5,4)$在$C$上,$k$为常数,$0<k<1$.按照如下方式依次构造点$P_n\\left(n=2,3,\cdots\right)$:过$P_{n-1}$作斜率为$k$的直线与$C$的左支交于点$Q_{n-1}$,令$P_n$为$Q_{n-1}$关于$y$轴的对称点,记$P_{n}$的坐标......
  • AT_hitachi2020_c ThREE 题解
    题意:给定一颗树,构造一个排列\(p\)使得对于每一对\((x,y),dis(x,y)=3\),有\(3\midp_x+p_y\)或\(3\midp_x\timesp_y\)。首先我们先将所有\(p_i\)都模上\(3\)。条件等价于每一对距离为\(3\)的\((x,y)\),\(p_x\)和\(p_y\)不同时为\(1\)或\(2\)。那先考虑如......
  • 嵌入式开发常见问题解决方法
    一、问题复现稳定复现问题才能正确的对问题进行定位、解决以及验证。一般来说,越容易复现的问题越容易解决。1.1模拟复现条件有的问题存在于特定的条件下,只需要模拟出现问题的条件即可复现。对于依赖外部输入的条件,如果条件比较复杂难以模拟可以考虑程序里预设直接进入对应......
  • Windows共享文件夹常见问题解决方法
    目录你不能访问此共享文件夹,因为你组织的安全策略阻止未经身份验证的来宾访问允许自己电脑去访问局域网其他电脑的共享文件允许局域网内别人电脑访问自己电脑的共享文件你不能访问此共享文件夹,因为你组织的安全策略阻止未经身份验证的来宾访问参考:https://blog.csdn.net/qq28574......
  • WPF阻止窗体被系统缩放,使用显示器DPI
    WPF默认是跟随系统DPI变化(缩放与布局)而缩放窗体的;微软把它称为默认DPI感知,当DPI发生变化时WPF感知到后缩放窗体,介绍链接:设置进程的默认DPI感知(Windows)-Win32apps|MicrosoftLearn如果我们不希望窗体被缩放,而是让窗体使用显示器DPI该怎么办呢?首先修改app.manifest,如......
  • 由AtCoder_ABC357D引发的除法同余学习
    鉴于最近的Atcoder周赛又出现除法求余,下定决心学习逆元相关内容同余概述定义同余定义:若a和b是整数,且m|(a-b),则称a和b模m同余。即两者除以m得到的余数相同。剩余系:一个模m完全剩余系是一个整数集合,任何一个整数恰好与该集合中的一个元素模m同余。例如0,1,...,m-1的集......
  • 启动应用程序出现efsui.exe找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个efsui.exe文件(挑选合适的版本文件)把它放入......
  • 启动应用程序出现findstr.exe找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个findstr.exe文件(挑选合适的版本文件)把它放......