长春seo公司网站,南平建设集集团网站,施工企业的定义,易营宝智能建站动态规划Ⅰ 一、基础1. 意义2. 序列 dp 解法 二、例题1. 最大子段和2. 删数最大子段和#xff08;数据强度#xff1a;pro max#xff09;3. 最长上升子序列#xff08;数据强度#xff1a;pro max#xff09;4. 3 或 5 的倍数序列5. 数码约数序列 一、基础
1. 意义
动… 动态规划Ⅰ 一、基础1. 意义2. 序列 dp 解法 二、例题1. 最大子段和2. 删数最大子段和数据强度pro max3. 最长上升子序列数据强度pro max4. 3 或 5 的倍数序列5. 数码约数序列 一、基础
1. 意义
动态规划dynamic programming简称 dp将一个目标大问题“大事化小小事化了”分成很多的子问题得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。 #mermaid-svg-gEhLDVS2DZrOJtNp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .error-icon{fill:#552222;}#mermaid-svg-gEhLDVS2DZrOJtNp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-gEhLDVS2DZrOJtNp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-gEhLDVS2DZrOJtNp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-gEhLDVS2DZrOJtNp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-gEhLDVS2DZrOJtNp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-gEhLDVS2DZrOJtNp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-gEhLDVS2DZrOJtNp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-gEhLDVS2DZrOJtNp .marker.cross{stroke:#333333;}#mermaid-svg-gEhLDVS2DZrOJtNp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-gEhLDVS2DZrOJtNp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .cluster-label text{fill:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .cluster-label span{color:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .label text,#mermaid-svg-gEhLDVS2DZrOJtNp span{fill:#333;color:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .node rect,#mermaid-svg-gEhLDVS2DZrOJtNp .node circle,#mermaid-svg-gEhLDVS2DZrOJtNp .node ellipse,#mermaid-svg-gEhLDVS2DZrOJtNp .node polygon,#mermaid-svg-gEhLDVS2DZrOJtNp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-gEhLDVS2DZrOJtNp .node .label{text-align:center;}#mermaid-svg-gEhLDVS2DZrOJtNp .node.clickable{cursor:pointer;}#mermaid-svg-gEhLDVS2DZrOJtNp .arrowheadPath{fill:#333333;}#mermaid-svg-gEhLDVS2DZrOJtNp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-gEhLDVS2DZrOJtNp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-gEhLDVS2DZrOJtNp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-gEhLDVS2DZrOJtNp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-gEhLDVS2DZrOJtNp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-gEhLDVS2DZrOJtNp .cluster text{fill:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp .cluster span{color:#333;}#mermaid-svg-gEhLDVS2DZrOJtNp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-gEhLDVS2DZrOJtNp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 问题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 0∼i 中 …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 n≤100。 对于 80 % 80\% 80% 的数据 n ≤ 5000 n≤5000 n≤5000。 对于 100 % 100\% 100% 的数据 n ≤ 100000 n≤100000 n≤100000。 【问题类型】 取子段 【问题解法】 dp[i] 表示以 a[i] 为结尾的最大子段和是多少 【模板技巧】 如果前面都是负数我不跟它们同流合污a[i]如果前面大的那就加入它们做一个更大的数dp[i-1]a[i] 【参考答案】
#includebits/stdc.h
using namespace std;
int n,maxn-1e8;
int a[100005];
int dp[100005];
int main(){cinn;for(int i1;in;i)cina[i];dp[1]a[1];for(int i2;in;i){dp[i]max(a[i],dp[i-1]a[i]);maxnmax(maxn,dp[i]);}coutmaxn;return 0;
}2. 删数最大子段和数据强度pro max
给出一个数组 a[]删除一个元素后求它的最大子段和。子段是指数组中连续的一段元素删除的元素可以由你自由选择但是不能不删除任何元素输出你能得到的最大的子段和。
思路要删掉 a[i] 的时候会产生两个切口第一个是以 a[i-1] 为结尾第二个是以 a[i1] 为开头。以 a[i-1] 为结尾取一个非常大的子段以 a[i1] 为开头取一个非常大的子段将它们组合在一起就可以完成本题。
#includebits/stdc.h
#define int long long
using namespace std;
const int MAXN1e68;
const int NEGINF-1e18;
int n,ansNEGINF;
int a[MAXN],dpl[MAXN],dpr[MAXN];
/*
* dpl[i]:以i为右端点的最大子段和
* dpr[i]:以i为左端点的最大子段和
*/
signed main(){cinn;for(int i1;in;i)cina[i];for(int i1;in;i)dpl[i]max(dpl[i-1]a[i],a[i]);for(int in;i1;i--)dpr[i]max(dpr[i1]a[i],a[i]);for(int i1;in;i)ansmax({ans,dpl[i-1],dpr[i1],dpl[i-1]dpr[i1]});//选择左边/右边/左边和右边coutans;return 0;
}3. 最长上升子序列数据强度pro max
求出数组 a[] 的最长上升子序列⻓度。
参考答案
#includebits/stdc.h
using namespace std;
int n,sz;
int a[5005];
int dp[5005];
int main(){cinn;for(int i1;in;i)cina[i];for(int i1;in;i){if(sz0||a[i]dp[sz])sz,dp[sz]a[i];else{int plower_bound(dp1,dpsz1,a[i])-dp;dp[p]a[i];}}coutsz;return 0;
}4. 3 或 5 的倍数序列
给出一个序列 a[]要求你从中找出一个子序列满足子序列中任意相邻两数之和是 3 3 3 或 5 5 5 的倍数。
#includebits/stdc.h
using namespace std;
const int MAXN3e38;
const int MOD1e97;
int n,a[MAXN],dp[MAXN];
int main(){cinn;for(int i1;in;i)cina[i];int ans0;for(int i1;in;i){for(int j1;ji;j)if((a[i]a[j])%30||(a[i]a[j])%50)dp[i](dp[i]dp[j]1)%MOD;ans(ansdp[i])%MOD;}coutans;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 的约数。 问所有满足要求的子序列中总和最大的序列的和是多少单独一个数也算满足要求的序列
#includebits/stdc.h
using namespace std;
const int MAXN1e58;
long long n,dp[MAXN][10];
int main(){cinn;for(int i1,a,fst,lst;in;i){cina,fsta,lsta%10;while(fst10)fst/10;for(int j0;j9;j)dp[i][j]dp[i-1][j];for(int j1;jfst;j)if(fst%j0)dp[i][lst]max(dp[i][lst],dp[i-1][j]a);}long long ans0;for(int i0;i9;i)ansmax(ans,dp[n][i]);coutans;return 0;
}
