网站建设都需要什么费用,wordpress自定义钩子,黑科技引流推广神器下载,下载安装目录 1 基础知识2 模板3 工程化 1 基础知识
线性DP#xff1a;状态转移表达式存在明显的线性关系。 区间DP#xff1a;与顺序有关#xff0c;状态与区间有关。
2 模板
3 工程化
题目1#xff1a;数字三角形。
解题思路#xff1a;直接DP即可#xff0c;f[i][j]可以来… 目录 1 基础知识2 模板3 工程化 1 基础知识
线性DP状态转移表达式存在明显的线性关系。 区间DP与顺序有关状态与区间有关。
2 模板
3 工程化
题目1数字三角形。
解题思路直接DP即可f[i][j]可以来自f[i-1][j] a[i][j]和f[i-1][j-1] a[i][j]注意f[i-1][j]不存在的情况最后一个点和f[i-1][j-1]不存在的情况第一个点。
C代码如下
#include iostreamusing namespace std;const int N 510;
int n;
int a[N][N];
int f[N][N];int main() {cin n;for (int i 0; i n; i) {for (int j 0; j i 1; j) {cin a[i][j];}}for (int i 0; i N; i) {for (int j 0; j N; j) {f[i][j] -0x3f3f3f3f;}}f[0][0] a[0][0];for (int i 1; i n; i) {for (int j 0; j i 1; j) {f[i][j] max(f[i][j], f[i-1][j] a[i][j]);if (j - 1 0) f[i][j] max(f[i][j], f[i-1][j-1] a[i][j]);}}int res -0x3f3f3f3f;for (int j 0; j n; j) res max(res, f[n-1][j]);cout res endl;return 0;
}题目2最长上升子序列。注意可以连续比如3 1 2 1 8 5 6那么它的最长上升子序列为1 2 5 6长度为4。
解题思路DP即可。
状态定义f[i]表示以第 i i i元素结尾的上升子序列的最大长度。
状态转移有
没有上一个元素即f[i] 1。从第 i − 1 i-1 i−1个元素转移过来需要满足a[i-1] a[i]则f[i-1] 1。从第 i − 2 i-2 i−2个元素转移过来需要满足a[i-2] a[i]则f[i-2] 1。 ……从第 0 0 0个元素转移过来需要满足a[0] a[i]则f[0] 1。
C代码如下
#include iostreamusing namespace std;const int N 1010;
int n;
int a[N];
int f[N];int main() {cin n;for (int i 0; i n; i) cin a[i];for (int i 0; i n; i) {f[i] 1;for (int j 0; j i; j) {if (a[j] a[i]) f[i] max(f[i], f[j] 1);} }int res 0;for (int i 0; i n; i) res max(res, f[i]);cout res endl;return 0;
}同时输出最长上升子序列那么此时只需要记住当前状态是从哪一个状态转移过来的然后逆序输出即可。C代码如下
#include iostream
#include algorithmusing namespace std;const int N 1010;
int n;
int a[N];
int f[N];
int g[N];int main() {cin n;for (int i 0; i n; i) cin a[i];for (int i 0; i n; i) {f[i] 1;g[i] -1; //g[i]-1表示它是子序列的起点for (int j 0; j i; j) {if (a[j] a[i]) {if (f[i] f[j] 1) {f[i] f[j] 1;g[i] j;//g[i]j表示状态f[i]是从状态f[j]转移过来的}}} }int res 0;for (int i 0; i n; i) {if (f[i] f[res]) {res i;}}cout f[res] endl;//输出最长子序列的长度vectorint ans; //最长子序列for (int i res; i ! -1; i g[i]) {ans.emplace_back(a[i]);}reverse(ans.begin(), ans.end());for (int i 0; i ans.size(); i) cout ans[i] ;cout endl;return 0;
}测试样例
输入
7
3 1 2 1 8 5 6
输出
4
1 2 5 6 题目3最长公共子序列给定字符串a和字符串b求它们的最长公共子序列。例如acbd和abedc则它们的最长公共子序列为abd长度为3。
思路利用DP来求解由于这里求的是最大长度因此在状态转移时可以适当放大以便可以表示相应转移路径。
状态定义f[i][j]从字符串a前i个中选且从字符串b中前j个中选的公共子序列的最大长度。
状态转移有
a[i]不在最优公共子序列当中b[j]不在最优公共子序列当中则f[i-1][j-1]。a[i]在最优公共子序列当中b[j]不在最优公共子序列当中无法表示故将其放大为f[i][j-1]。a[i]不在最优公共子序列当中b[j]在最优公共子序列当中无法表示故将其放大为f[i-1][j]。a[i]在最优公共子序列当中b[j]在最优公共子序列当中要求a[i]b[j]则f[i-1][j-1] 1。
进一步思考由于进行了放大因此第2种情况和第3种情况包含了第1种情况。因此在代码实现时可以考虑如下状态转移f[i][j-1]、f[i-1][j]和f[i-1][j-1] 1。
C代码如下
#include iostreamusing namespace std;const int N 1010;
char a[N], b[N];
int n, m;
int f[N][N];int main() {cin n m;cin a 1 b 1;for (int i 1; i n; i) {for (int j 1; j m; j) {f[i][j] max(f[i-1][j], f[i][j-1]);if (a[i] b[j]) f[i][j] max(f[i][j], f[i-1][j-1] 1);}}cout f[n][m] endl;return 0;
}题目4合并相邻石子的最小代价。例如1 3 5 2合并前两堆石子1和3的代价是4得到4 5 2。
解题思路区间合并类DP状态定义围绕着区间然后怎么层层递进计算状态比较考验。答案是枚举区间长度来计算。
状态定义f[i][j]合并第i~j堆石子的最小代价。
状态转移有
最后一次合并为[i,i]和[i1,j]这两个区间合并即f[i][i] f[i 1][j] s[j] - s[i - 1]其中s[i]表示前缀和。最后一次合并为[i,i1]和[i2,j]这两个区间合并即f[i][i 1] f[i 2][j] s[j] - s[i - 1]。最后一次合并为[i,i2]和[i3,j]这两个区间合并即f[i][i 2] f[i 3][j] s[j] - s[i - 1]。 ……最后一次合并为[i,j-1]和[j,j]这两个区间合并即f[i][j - 1] f[j][j] s[j] - s[i - 1]。
初始化f[i][i]0然后其余初始化为正无穷大比如1e9。
最终答案为f[1][n]。
注意状态的遍历是通过区间长度从1到n实现的。
C代码如下
#include iostreamusing namespace std;const int N 310;
int a[N];
int s[N];
int f[N][N];
int n;int main() {cin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i) s[i] s[i-1] a[i];for (int len 2; len n; len) {//枚举左端点for (int i 0; i len - 1 n; i) {int l i, r i len - 1;f[l][r] 1e9;for (int k l; k r; k) {f[l][r] min(f[l][r], f[l][k] f[k1][r] s[r] - s[l-1]);}}}cout f[1][n] endl;return 0;
}
