POJ-动态规划-典型问题模板

动态规划典型问题模板

一、最长上升子序列（Longest increasing subsequence）

状态：以ak(k=1,2,3...N)为终点的最长递增子序列的长度。

状态转移方程：

MaxLen(1) = 1MaxLen(k) = Max{ MaxLen(i): 1<i<k 且 a_i<a_k 且 k≠1 } +1

这个转移方程的意思就是，MaxLen(k)的值，就是在a_k左边，“终点”数值小于a_k，且长度最大的那个上升子序列的长度再加1。因为a_k左边任何“终点”小于a_k的子序列，加上a_k后就能形成一个更长的子序列。

注意：读入数据和状态转移都以1为起点。

数据结构：

const int N = 10010; int a[N];//记录原序列 int dp[N];//dp[i]表示包括第i位之前序列的最长上升子序列长度 int len;//原序列长度

LIS()：动规求解序列各位的最长递增子序列长度

int LIS() { int tmp = 1;//返回值，表示整个序列的LIS值 for (int i = 1; i <= len; i++) { dp[i] = 1;//都初始化为1,方便后面直接比较 for (int j = 1; j < i; j++) { if (a[j]<a[i] && dp[j] + 1>dp[i]) dp[i] = dp[j] + 1; } if (dp[i] > tmp) tmp = dp[i]; } return tmp; }

例：POJ 2533 Longest Ordered Subsequence

AC代码

#include<cstdio> #include<cstring> const int N = 1010; int a[N];//记录原序列 int dp[N];//dp[i]表示包括第i位之前序列的最长上升子序列长度 int len;//原序列长度 int LIS() { int tmp = 1;//返回值，表示整个序列的LIS值 for (int i = 1; i <= len; i++) { dp[i] = 1;//都初始化为1,方便后面直接比较 for (int j = 1; j < i; j++) { if (a[j]<a[i] && dp[j] + 1>dp[i]) dp[i] = dp[j] + 1; } if (dp[i] > tmp) tmp = dp[i]; } return tmp; } int main() { scanf("%d", &len); for (int i = 1; i <= len; i++)scanf("%d", &a[i]); int ans = LIS(); printf("%d", ans); return 0; } #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int N = 1005; int n; int a[N]; int dp[N]; int LIS() { int ans = 1; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (dp[j] + 1 > dp[i] && a[j] < a[i])dp[i] = dp[j] + 1; } if (dp[i] > ans)ans = dp[i]; } return ans; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++)scanf("%d", &a[i]); printf("%d\n", LIS()); //system("pause"); return 0; } 二刷

转载于:https://www.cnblogs.com/yun-an/p/11108418.html