网站策划设计建设,图片生成器软件,企业管理咨询服务协议,ktv网站建设今天的三个题目属于模板题#xff0c;可能将来会遇见它们的变形应用。
1、最长上升子序列问题 这道题目的关键就在于我们的状态定义#xff0c;我们定义#xff1a;f(i)表示长度为i的子序列的末尾最大值。意思就是#xff0c;比如一个子序列为#xff1a;1,4,5#xff0…今天的三个题目属于模板题可能将来会遇见它们的变形应用。
1、最长上升子序列问题 这道题目的关键就在于我们的状态定义我们定义f(i)表示长度为i的子序列的末尾最大值。意思就是比如一个子序列为1,4,5那么按我们的集合定义就应该是f(3) 5。这样定义了话我们就可以很容易的解题我们只需要从头到尾遍历数组找到当前数大于的最小值然后更新找到的f。举个例子f(2) 3 f(3) 5,这时候我们当前数是4,那么我们就把4接到3之后也就是f(3) 4。这里其实用到了贪心的思想我们让不同长度的末尾值尽可能小这样最长长度一定会尽可能长。代码你可以直接暴力寻找也可以二分查找都可以。
#include iostream//直接暴力using namespace std;const int N 1010;
int f[N] ,a[N] ,n;int main()
{cin n;for (int i 1 ;i n ;i ) cin a[i];for (int i 1 ;i n ;i ){f[i] 1;for (int j 1 ;j i ;j ){if (a[i] a[j]) f[i] max(f[i] ,f[j] 1);}}int res -1;for (int i 1 ;i n ;i ) res max(res ,f[i]);cout res;return 0;
}
#include iostream//二分
#include cstdio
#include algorithm
#include cstringusing namespace std;#define N 100100int f[N] ,len ,a[N] ,n;int main()
{cin n;for (int i 1 ;i n ; i) cin a[i];f[0] -2e9;for (int i 1 ;i n ;i ){int l 0 ,r len;while (l r){int mid (l r 1) / 2;if (a[i] f[mid]) l mid;elser mid - 1;}len max(len ,r 1);f[r 1] a[i];}cout len;return 0;
}
2、最长公共子序列 这个题目的dp思路是定义一个集合f(i ,j)表示字符串A的前i个字符以及字符串B的前j个字符中最长公共字符串长度。状态划分就可以是1、a[i] b[j]时f[i][j] f[i - 1][j - 1] 1。2、a[i] ! b[j]时最大公共字符串一定在A的前i - 1个字符和B的前j个字符 或者说A的前i个字符和B的前j - 1个字符中因此f[i][j] max(f[i - 1][j] ,f[i][j - 1])。
#include iostream
#include cstdio
#include algorithm
#include cstringusing namespace std;#define N 1100int f[N][N] ,n ,m;
char a[N] ,b[N];int main()
{cin n m;scanf(%s ,a 1);scanf(%s ,b 1);f[0][0] 0;for (int i 1 ;i n ;i )for (int j 1 ;j m ;j ){if (a[i] b[j]) f[i][j] f[i - 1][j - 1] 1;f[i][j] max(f[i - 1][j] ,f[i][j]);f[i][j] max(f[i][j - 1] ,f[i][j]);}cout f[n][m];return 0;
}
3、最长公共上升子序列 这道题的思路是前两道题的结合版本更加的复杂很难想到。f(i ,j)表示第一个序列前i个字母以及第二个序列前j个字母并且以b[j]结尾的公共上升子序列的最大值。那么我们的状态划分就可以分为两大类一、a[i] b[j]的时候最大公共上升序列跟a[i]无关那么状态转移:f[i][j] f[i - 1][j]。二、a[i] b[j]的时候最大公共上升序列的末尾就是a[i] ,那么我们就根据倒数第二个值是哪一个划分状态f[i][j] max(f[i - 1][1] ,f[i - 1][2] .......f[i - 1][j - 1])。根据这个思路我们写出代码
#include iostream
#include algorithm
#include cstdio
#include cstringusing namespace std;#define N 3500
#define ll long longll f[N][N] ,n ,a[N] ,b[N];int main()
{cin n;for (int i 1 ;i n ;i ) cin a[i];for (int j 1 ;j n ;j ) cin b[j];for (int i 1 ;i n ;i ){for (int j 1 ;j n ;j ){ll maxv 1;//作为中间值存取f(i - 1 ,1 ~ j - 1)的最大值f[i][j] f[i - 1][j];if (a[i] b[j]){for (int k 1 ;k j ;k ){if (a[i] b[k]) maxv max(maxv ,f[i - 1][k] 1);//注意必须a[i] b[k]否则就不能满足递增序列的条件。}f[i][j] max(f[i][j] ,maxv);}}}ll ans -1e9;for (int i 1 ;i n ; i ) ans max(ans ,f[n][i]);cout ans;return 0;
} 三重循环n方复杂度很明显时间复杂度太高我们考虑优化。根据代码我们可以看出在i确定的情况下f[i][k - 1]的值是跟j没有关系的我们就可以优化掉第三层循环
#include iostream
#include algorithm
#include cstdio
#include cstringusing namespace std;#define N 3050int f[N][N] ,n ,a[N] ,b[N];int main()
{cin n;for (int i 1 ;i n ;i ) cin a[i];for (int j 1 ;j n ;j ) cin b[j];for (int i 1 ;i n ;i ){int maxv 1;for (int j 1 ;j n ;j ){f[i][j] f[i - 1][j];if (a[i] b[j]) f[i][j] max(f[i][j] ,maxv);if (a[i] b[j]) maxv max(maxv ,f[i - 1][j] 1);}}int ans 0;for (int i 1 ;i n ; i ) ans max(ans ,f[n][i]);cout ans;return 0;
}
