1最长上升子序列分析与昨天我们讲解的几道题不太一样这是一道线性dp题而不是背包问题。这道题是一道线性dp的板子题我们分析其题意要求求出题目中给出的序列的最长上升子序列的长度这个序列是线性的当然也要用线性方法来找因此是线性dp。分析dp要求的结果最长上升子序列的长度。所以设dp[i]表示以第i个元素结尾的最长上升子序列的长度。此时我们确定了dp的状态由于每个元素本身至少可以构成一个长度为 1 的子序列所以初始化dp[i] 1。状态转移方程对于每个i我们需要遍历它前面的所有元素j0 j i。如果nums[j] nums[i]满足上升条件那么nums[i]就可以接在以nums[j]结尾的子序列后面。转移方程为dp[i] max(dp[i],dp[j] 1)由此我们可以写出如下代码#includebits/stdc.h using namespace std; int a[5020],dp[5600],n;//初始化 int main(){ cinn; for (int i 0;i n;i) cina[i];//输入 for (int i 0;i n;i) dp[i] 1;//每个元素本身至少可以构成一个长度为1的子序列 for (int i 0;i n;i)//外层每个位置1-n结尾的最长上升子序列长度 for(int j 0;j i;j) if(a[i] a[j])//如果前面的元素a[j]严格小于当前元素a[i]满足上升条件 dp[i] max(dp[i],dp[j]1);//状态转移 int ans 0; for (int i 0;i n;i) ans max(ans,dp[i]);//求出最大正解 coutans;//输出 return 0; }2合唱队形分析先看看要求我们求出什么。题目的输出要求是最少需要出列的人数这个队列是线性的所以本题是线性dp。接下来定义dp[i]表示什么由于dp[]中存在答案所以dp中的值与答案的含义类似。题目要求剩下的同学排成“先严格递增后严格递减”的队形并且要求出列的人数最少。这说明我们需要分两步来完成dp第一次完成上升的第二次为下降的。left_dp[i]表示以第i个元素结尾的从左往右看最长严格上升子序列的长度。right_dp[i]表示为以第i个元素开头的从左往右看最长严格下降子序列的长度。接下来确定状态转移公式if (a[i] a[j]) dp[i] max(dp[i],dp[j]1);我们来确定一下为何要这样写。含义判断条件。检查第 j 个元素是否严格小于第 i 个元素。作用只有当 a[j] a[i] 时a[i] 才有资格接在 a[j] 的后面从而满足“上升”的条件。如果不满足这个条件a[i] 就无法和 a[j] 连起来直接跳过。dp[j] 1表示假设我们把 a[i] 接在以 a[j] 结尾的子序列后面那么新的子序列长度就是 dp[j] 的长度加上 a[i] 自己的 1。因为你现在正在处理第 i 个元素 a[i]并且你发现 a[i] a[j]。这就意味着你可以把 a[i] 直接插到原来那个队伍的末尾。此时我们就出现了dp[j]在家上一个多的dp[i]总和是dp[j]1。由此一来我们便可以开始构建代码了#includebits/stdc.h using namespace std; int n,a[120]; int dp[120],dp2[120]; int main(){ cinn; for (int i 1;i n;i){ cina[i]; dp[i] dp2[i] 1;//依然是照搬上题的初始化 } for (int i 1;i n;i){//内部从1-n每一个的解 for (int j 1;j i;j){//往左边看形成上升子序列 if (a[i] a[j])//只有前面的同学比当前同学矮才能接上 dp[i] max(dp[i],dp[j]1);//状态转移构建当前答案 } } for(int i n;i 1;i--)//往回看下降 for(int j n;j i;j--)从n到i最长下降子序列 if(a[i] a[j]) //依然是这个上升下降的公用判断 dp2[i] max(dp2[i],dp2[j]1);//状态转移 int maxn 0; for (int i 1;i n;i) maxn max(dp[i]dp2[i]-1,maxn);//最后算出dp1和2两次的总答案由于每次个包含一半把中间点包含两次所以-1。 coutn-maxn;//我们算的是留下几位同学这里把留下的减掉就是出去 return 0; }