ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客小白月赛53]D.Breezing(DP)

2022年7月9日 142点热度 0人点赞 0条评论

题目链接:D-Breezing_牛客小白月赛53 (nowcoder.com)

题目 / Problem

给定一个序列B,让我们生成一个序列A,要求Ai∈[1, Bi],且使得从∑[2, N] abs(a[i] - a[i - 1])最大。求出这个最大值。

思路 / Thought

显然这里应该的Ai要么取1,要么取Bi,因为这两种方案总是比取中间的一样或者更好。

如果按照朴素的想法可能进行dfs,也就是说每个位置,也就是每一层有两种选择,1或者Bi,但是这样时间复杂度就达到了O(2^N)十分惊人。

于是考虑到“大部分的序列中的dfs都可以由DP代替”,于是考虑用dp来解决这道题。

第一步确定dp状态。这里每个状态由两个值决定:位置和数字。

而数字只有两种选择:“最小值1”或者“最大值Bi”。

于是我们用dp[pos][0/1]来表示所有状态,其中第二维中0表示这一位数字是1,而1表示数字是Bi。

再想一下状态转移方程,dp[i][0]可以由dp[i-1][0]和dp[i-1][1]转移过来,dp[i][1]也一样,只需要取个大的就可以了,非常简单。

状态转移方程

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int dp[maxn][2];

inline int getabs(int x){return x < 0 ? -x : x;}

signed main()
{
    ios::sync_with_stdio(0);
    int N;cin >> N;
    vector<int> b(N + 1);
    for(int i = 1;i <= N; ++ i)cin >> b[i];
    
    for(int i = 2;i <= N; ++ i)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + b[i - 1] - 1);
        dp[i][1] = max(dp[i - 1][1] + getabs(b[i - 1] - b[i]), dp[i - 1][0] + b[i] - 1);
    }
    
    cout << max(dp[N][0], dp[N][1]) << '\n';
    
    return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP 动态规划 小白月赛 牛客网 算法 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号