当前位置: 首页 > news >正文

贵州专业网站建设公司查询域名注册信息

贵州专业网站建设公司,查询域名注册信息,做网站延期交付了,网站做背景不显示动态规划Ⅰ 一、基础1. 意义2. 序列 dp 解法 二、例题1. 最大子段和2. 删数最大子段和(数据强度:pro max)3. 最长上升子序列(数据强度:pro max)4. 3 或 5 的倍数序列5. 数码约数序列 一、基础 1. 意义 动…

动态规划Ⅰ

  • 一、基础
    • 1. 意义
    • 2. 序列 dp 解法
  • 二、例题
    • 1. 最大子段和
    • 2. 删数最大子段和(数据强度:pro max)
    • 3. 最长上升子序列(数据强度:pro max)
    • 4. 3 或 5 的倍数序列
    • 5. 数码约数序列

一、基础

1. 意义

动态规划(dynamic programming,简称 dp,将一个目标大问题“大事化小,小事化了”,分成很多的子问题,得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。

问题P
子问题P1
子问题P1的解
问题P的解
子问题P2
子问题P2的解
子问题P3
子问题P3的解
子问题P4
子问题P4的解

2. 序列 dp 解法

序列型动态规划分为几种常见的问题:

  • 取连续的子段(串)
    • dp[i] 表示以 i i i 为结尾
  • 取子序列(不要求连续)
    • dp[i] 表示以 i i i 为结尾
    • dp[i] 表示 0 ∼ i 0\sim i 0i 中 …
    • dp[i] 长度为 i i i 序列结尾的性质
  • 分段
    • dp[i] 表示以 i i i 为结尾

二、例题

1. 最大子段和

题目描述

给出数组 a a a,如果我们取连续且非空的一段,那么这段的和最大是多少?

输入描述

1 1 1 行,是一个正整数 n n n,数组 a a a 的长度。
2 2 2 行,用空格隔开的 n n n 个整数,依次是 a [ 1 ] ∼ a [ n ] a[1]\sim a[n] a[1]a[n] 的值。

输出描述

1 1 1 个整数,为所求的最大的和

样例1

输入

6
1 -6 5 -4 2 4

输出

7

提示

【样例解释】
5 , − 4 , 2 , 4 5,−4,2,4 5,4,2,4 可以得到最大的和 7 7 7
【数据范围】
对于 60 % 60\% 60% 的数据, n ≤ 100 n≤100 n100
对于 80 % 80\% 80% 的数据, n ≤ 5000 n≤5000 n5000
对于 100 % 100\% 100% 的数据, n ≤ 100000 n≤100000 n100000

【问题类型】 取子段
【问题解法】 dp[i] 表示以 a[i] 为结尾的最大子段和是多少
【模板技巧】 如果前面都是负数,我不跟它们同流合污(a[i]);如果前面大的,那就加入它们,做一个更大的数(dp[i-1]+a[i]
【参考答案】

#include<bits/stdc++.h>
using namespace std;
int n,maxn=-1e8;
int a[100005];
int dp[100005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dp[1]=a[1];for(int i=2;i<=n;i++){dp[i]=max(a[i],dp[i-1]+a[i]);maxn=max(maxn,dp[i]);}cout<<maxn;return 0;
}

2. 删数最大子段和(数据强度:pro max)

给出一个数组 a[],删除一个元素后,求它的最大子段和。(子段是指数组中连续的一段元素)删除的元素可以由你自由选择,但是不能不删除任何元素,输出你能得到的最大的子段和。

思路:要删掉 a[i] 的时候会产生两个切口,第一个是以 a[i-1] 为结尾,第二个是以 a[i+1] 为开头。以 a[i-1] 为结尾取一个非常大的子段,以 a[i+1] 为开头取一个非常大的子段,将它们组合在一起,就可以完成本题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+8;
const int NEGINF=-1e18;
int n,ans=NEGINF;
int a[MAXN],dpl[MAXN],dpr[MAXN];
/*
* dpl[i]:以i为右端点的最大子段和
* dpr[i]:以i为左端点的最大子段和
*/
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)dpl[i]=max(dpl[i-1]+a[i],a[i]);for(int i=n;i>=1;i--)dpr[i]=max(dpr[i+1]+a[i],a[i]);for(int i=1;i<=n;i++)ans=max({ans,dpl[i-1],dpr[i+1],dpl[i-1]+dpr[i+1]});//选择左边/右边/左边和右边cout<<ans;return 0;
}

3. 最长上升子序列(数据强度:pro max)

求出数组 a[] 的最长上升子序列⻓度。

参考答案:

#include<bits/stdc++.h>
using namespace std;
int n,sz;
int a[5005];
int dp[5005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(sz==0||a[i]>dp[sz])sz++,dp[sz]=a[i];else{int p=lower_bound(dp+1,dp+sz+1,a[i])-dp;dp[p]=a[i];}}cout<<sz;return 0;
}

4. 3 或 5 的倍数序列

给出一个序列 a[],要求你从中找出一个子序列,满足子序列中任意相邻两数之和是 3 3 3 5 5 5 的倍数。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e3+8;
const int MOD=1e9+7;
int n,a[MAXN],dp[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++)if((a[i]+a[j])%3==0||(a[i]+a[j])%5==0)dp[i]=(dp[i]+dp[j]+1)%MOD;ans=(ans+dp[i])%MOD;}cout<<ans;return 0;
}

5. 数码约数序列

给出一个序列 a[],要求你从中找出一个子序列,满足子序列中任意相邻两数,前一个数的末位数码是后一个数的首位数码的约数。
例如 302 , 817 , 739000 302,817,739000 302,817,739000 是一个满足要求的序列,因为 302 302 302 的末位 2 2 2 807 807 807 的首位 8 8 8 的约数; 817 817 817 的末位 7 7 7 739000 739000 739000 的首位 7 7 7 的约数。 但是 70 , 1 70,1 70,1 就不满足要求,因为 0 0 0 不是 1 1 1 的约数。
问所有满足要求的子序列中,总和最大的序列的和是多少?(单独一个数也算满足要求的序列)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
long long n,dp[MAXN][10];
int main(){cin>>n;for(int i=1,a,fst,lst;i<=n;i++){cin>>a,fst=a,lst=a%10;while(fst>=10)fst/=10;for(int j=0;j<=9;j++)dp[i][j]=dp[i-1][j];for(int j=1;j<=fst;j++)if(fst%j==0)dp[i][lst]=max(dp[i][lst],dp[i-1][j]+a);}long long ans=0;for(int i=0;i<=9;i++)ans=max(ans,dp[n][i]);cout<<ans;return 0;
}
http://www.khdw.cn/news/20610.html

相关文章:

  • 网站建设的公司推荐淘宝代运营公司排名
  • 河北城乡建设厅网站百度知道在线问答
  • 高端网站设计报价表哪里有培训网
  • 深圳怎么做网站微信营销推广方案
  • 邳州网站建设广东最新疫情
  • 自家房子做民宿的网站市场营销互联网营销
  • 济源网站制作最好的免费推广平台
  • 曲靖手机网站建设昆明抖音推广
  • 佘山网站建设百度提交网址入口
  • 网站制作怎么创业河南网站排名
  • 做网站开视频网站游戏推广代理加盟
  • 个人网站建设培训竞价排名规则
  • 房山营销型网站建设哈尔滨最新消息
  • 国外做游戏的视频网站有哪些视频seo优化教程
  • 宜昌平台网站建设近10天的时事新闻
  • 做网站那里做可靠晨阳seo顾问
  • 化妆品网页设计论文seo优化seo外包
  • 注册公司费用是多少网站seo内容优化
  • 朔州推广型网站建设网络营销措施有哪些
  • 营销培训课程有哪些旺道seo系统
  • 怎么做免费的网站链接2022年新闻大事
  • wordpress 怎样写函数长沙企业seo服务
  • 怎样做网站呢长春网站制作计划
  • 网站有后台更新不了培训网站推广
  • 香港网站速度慢广州百度关键词搜索
  • 做网站生意不赚钱怎样推广品牌
  • 深圳做网站(官网)seo站长工具是什么
  • 什么网站可以买世界杯seo提升排名
  • 武汉防役新动态宁波seo外包服务
  • 企业为什么做网站优化推广网站流量统计系统