由于我之前写过一篇关于dp算法的文章了所以这里就不多阐释关于dp的内容了详情请见这篇文章【C竞赛】note动态规划DP接下来让我们看几道题来让我们更好感受一下dp的使用。版权说明以下所有题目均来自于洛谷例题一、模版题B3637 最长上升子序列题目如下B3637 最长上升子序列题目描述这是一个简单的动规板子题。给出一个由n ( n ≤ 5000 ) n(n\le 5000)n(n≤5000)个不超过10 6 10^6106的正整数组成的序列。请输出这个序列的最长上升子序列的长度。最长上升子序列是指从原序列中按顺序尽可能多取出一些数字排在一起这些数字是逐渐增大的。输入格式第一行一个整数n nn表示序列长度。第二行有n nn个整数表示这个序列。输出格式一个整数表示答案。输入输出样例 #1输入 #16 1 2 4 1 3 4输出 #14说明/提示分别取出1 11、2 22、3 33、4 44即可。题目分析如果一个上升子序列的最大值小于一个在它后面的数那么这个数和这个子序列可以拼成一个更长的上升子序列。意思是给你一串数字要你按顺序挑出尽量多的数字而且挑出来的数字必须一个比一个大严格递增。接下来我们分析一下样例一在样例一中的数据1 2 4 1 3 4可以挑1,2,3,4位置是1,2,5,6长度是4。也可以挑1,2,4但只有3所以最长是4。而我们要做的是这样一件事不管整个序列怎么组成我只管‘以当前这个数字作为结尾最长能有多长。要想知道它我就扫描它前面所有比它小的数字看谁结尾的长度最大我就在谁后面接上自己。所以接下来我们要一个a数组用来存数据,dp数组用来进行动态规划的部分。每个元素本身可以单独构成一个长度为 1 的子序列所以dp[i] 1。对于每个i ii枚举所有j i jiji如果a j a i a_ja_iaj​ai​那么就可以把a[i]接在a[j]结尾的最长上升子序列后面形成一个新的更长的子序列。因此状态转移方程为d p [ i ] max ⁡ ( 1 , max ⁡ j i a [ j ] a [ i ] ( d p [ j ] 1 ) ) dp[i] \max\left(1, \max_{\substack{j i \\ a[j] a[i]}} (dp[j] 1)\right)dp[i]max(1,maxjia[j]a[i]​​(dp[j]1))到此题目分析结束可以开始写代码了。AC代码#includebits/stdc.husingnamespacestd;intn;inta[5005];// 原始序列intdp[5005];// dp[i] 表示以 i 结尾的最长上升子序列长度intmain(){cinn;for(inti1;in;i){cina[i];}intans0;for(inti1;in;i){dp[i]1;// 以自身结尾长度至少为 1for(intj1;ji;j){if(a[j]a[i]){// 满足上升条件dp[i]max(dp[i],dp[j]1);}}ansmax(ans,dp[i]);// 更新全局最优解}coutans;return0;}接下来我们就要学会如何使用这个模板了下面一道题是dp的应用例题二、B3637 合唱队形P1091 [NOIP 2004 提高组] 合唱队形题目描述n nn位同学站成一排音乐老师要请其中的n − k n-kn−k位同学出列使得剩下的k kk位同学排成合唱队形。合唱队形是指这样的一种队形设k kk位同学从左到右依次编号为1 , 2 , 1,2,1,2,…, k ,k,k他们的身高分别为t 1 , t 2 , t_1,t_2,t1​,t2​,…, t k ,t_k,tk​则他们的身高满足t 1 ⋯ t i t i 1 t_1 \cdots t_it_{i1}t1​⋯ti​ti1​… t k ( 1 ≤ i ≤ k ) t_k(1\le i\le k)tk​(1≤i≤k)。你的任务是已知所有n nn位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。输入格式共二行。第一行是一个整数n nn2 ≤ n ≤ 100 2\le n\le1002≤n≤100表示同学的总数。第二行有n nn个整数用空格分隔第i ii个整数t i t_iti​130 ≤ t i ≤ 230 130\le t_i\le230130≤ti​≤230是第i ii位同学的身高厘米。输出格式一个整数最少需要几位同学出列。输入输出样例 #1输入 #18 186 186 150 200 160 130 197 220输出 #14说明/提示对于50 % 50\%50%的数据保证有n ≤ 20 n \le 20n≤20。对于全部的数据保证有n ≤ 100 n \le 100n≤100。题目分析由题得“他们的身高满足t 1 ⋯ t i t i 1 t_1 \cdots t_it_{i1}t1​⋯ti​ti1​… t k ( 1 ≤ i ≤ k ) t_k(1\le i\le k)tk​(1≤i≤k)”那意思是这个序列是先上升后下降的。那我们很容易就能看出我们需要正着算一遍序列再反着算一遍序列再给他们拼在一起减去中间那个计算重复的那就是答案。思路理清后我们就可以开始写代码了AC代码#includebits/stdc.husingnamespacestd;intn;inta[5005];intdp1[5005];intdp2[5005];intmain(){cinn;for(inti1;in;i){cina[i];}// 上升for(inti1;in;i){dp1[i]1;for(intj1;ji;j){if(a[j]a[i]){dp1[i]max(dp1[i],dp1[j]1);}}}// 下降for(intin;i1;i--){dp2[i]1;for(intjn;ji;j--){if(a[j]a[i]){dp2[i]max(dp2[i],dp2[j]1);}}}intans0;for(inti1;in;i){ansmax(ans,dp1[i]dp2[i]-1);}coutn-ansendl;}