****知識點****
最長遞增或遞減子系列（Longest Increasing/Decreasing Series，LIS/LDS）是指一個序列中按照單調性可構成最長單調的的序列，
最長公共子序列（Longest Common Series，LCS）是指兩個序列物件中共同包含的相同部分構成的子序列，可依據題意考慮單調性或不考慮，
最長子串（Longset Substring，LS）是指給定串中任意個連續的字符組成的子序列，
****入門題****
第一題：求一個字串的最長遞增子序列長度，如azbcdef的最長遞增子序列為abcdef，長度為6.
輸入：
第一行是一個整數N（0<N<20）,表示有N個字串需要處理；之后的N行為一個字串，串長度不超過1000.
輸出：
輸出字串的最長遞增子序列的長度，
解題分析：
有序列{a1,a2,a3,...,an},按照遞推求解的思想，用F[i]代表遞增子序列以ai結束時的最長長度，當i為1時即以a1結束時最長長度為1，則有F[1]=1.在除了長度為1
的情況以外，當i<x時如果滿足ai<ax，則ax可以跟在以ai結尾的遞增子序列之后形成新的遞增子序列，綜合兩種情況，可以得到最長遞增子序列的長度為:
（1）F[1];（2）F[1]+F（x），等價于F[x]=max{1,1+F[i]|ai<ax & i<x} （動態規劃經典）
注釋部分為解法1，非注釋部分為解法2.
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define maxn 10001 4 5 char s[maxn]; 6 int dp[maxn]; 7 int max_num; 8 9 /* 10 void LIS() 11 //最長子序列函式 12 { 13 int len; 14 memset(dp,0,sizeof(dp)); 15 //初始化dp陣列為0 16 len = strlen(s); 17 for(int i = 0; i < len; i++) 18 { 19 dp[i] = 1; 20 //未出現單調遞增情況時序列長度均初始化為1 21 for(int j = 0; j < i; j++) 22 //每滿足單調遞增條件：i>j,ai>aj 23 //同時滿足條件：i>j,dp[i]<dp[j]+1 24 //對序列長度進行F[i]=1+F[j] 25 { 26 if(s[i] > s[j] && dp[i] < dp[j] + 1) 27 dp[i] = 1 + dp[j]; 28 } 29 } 30 max_num = 0; 31 //初始化最長序列長度為0 32 //在下面找到dp陣列最大值輸出 33 for(int i = 0;i < len; i++) 34 if(max_num < dp[i]) 35 max_num = dp[i]; 36 } 37 38 39 int main(void) 40 { 41 int n; 42 while(scanf("%d",&n) != EOF) 43 { 44 while(n--) 45 { 46 scanf("%s",s); 47 //輸入每組字串 48 LIS(); 49 //呼叫最長序列長度求解函式 50 printf("%d\n",max_num); 51 //輸出 52 } 53 } 54 return 0; 55 } 56 */ 57 58 //以下方法主要是借鑒學習. 59 int main(void) 60 { 61 int n; 62 int max_num = 1; 63 int dp[maxn]; 64 dp[0] = -999; 65 //初始化dp陣列首元素,此處dp陣列為存盤陣列. 66 scanf("%d",&n); 67 while(n--) 68 { 69 scanf("%s",s); 70 //輸入字串 71 for(int i = 0; i < strlen(s); i++) 72 { 73 //比較每個輸入字串的字符 74 for(int j = max_num - 1; j >= 0; j--) 75 { 76 //只有在j=maxnum-1時滿足if條件才能繼續下一個字符 77 //否則需要替換dp中上一個存盤的字符來繼續下一個 78 if((int)s[i] > dp[j]) 79 { 80 dp[j+1] = s[i]; 81 //dp用于存盤最長子序列中字符 82 if(j + 1 == max_num) 83 max_num++; 84 break; 85 } 86 } 87 } 88 printf("%d\n",max_num-1); 89 //輸出最長遞增序列長度 90 } 91 return 0; 92 }
第二題：POJ2945 攔截導彈
描述：
某國為了防御敵國的導彈襲擊，開發出一種導彈攔截系統，但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于
前一發的高度，某天，雷達捕捉到敵國的導彈來襲，并觀測到導彈依次飛來的高度，請計算這套系統最多能攔截多少導彈，攔截來襲導彈時，必須按來襲導彈襲擊的時間順序，不允
許先攔截后面的導彈，再攔截前面的導彈，
輸入：
輸入有兩行，
第一行，輸入雷達捕捉到的敵國導彈的數量k（k<=25），
第二行，輸入k個正整數，表示k枚導彈的高度，按來襲導彈的襲擊時間順序給出，以空格分隔，
輸出：
輸出只有一行，包含一個整數，表示最多能攔截多少枚導彈，
樣例輸入：
8 300 207 155 300 299 170 158 65
樣例輸出：
6
解題分析：
設初始導彈的距離為d[i],之后每一發導彈的距離為d[j],當i>j時，根據題意要求每一發導彈高度都不高于前一發的高度即“≤”關系，轉換為等式關系：i>j時，d[i]≤d[j].與最長遞增子序列問題相比，本問題可以抽象為最長準遞減子序列（準為前后兩個距離可以相等的含義），針對導彈的距離序列為{a1,a2,a3,...,an},用F[i]代表導彈
距離序列以ai命中目標時的最高距離點，當i為1時即以a1結束時最高距離點為1，則有F[1]=1.在除了距離點數為1的情況以外，當i<x時如果滿足ai＞ax，則ax可以認為是以ai距離
處同一發導彈降落的距離點，綜合兩種情況，可以得到導彈最長準遞減子序列的長度為:
（1）F[1];（2）F[1]+F（x），等價于F[x]=max{1,1+F[i]|ai≥ax & i<x}
在攔截導彈問題的動態規劃AC代碼基礎上將LIS函式中的單調遞增條件：i>j,ai>aj 修改為i>j,ai≤aj即可，具體AC代碼如下：
1 //本質求單調最長遞減子序列 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 25; 6 int a[maxn],dp[maxn],m,Max; 7 8 void LDS() 9 { 10 memset(dp,0,sizeof(dp)); 11 for(int i = 0;i < m;i++) 12 { 13 dp[i] = 1; 14 //滿足條件i>j,ai<aj && i>j,dp[i]<dp[j]+1 15 for(int j = 0;j < i;j++) 16 if(a[i] <= a[j] ) 17 dp[i] = max(dp[i],dp[j]+1); 18 } 19 20 Max = 0; 21 //尋找dp陣列中最長序列數 22 for(int i = 0;i < m;i++) 23 if(Max < dp[i]) 24 Max = dp[i]; 25 } 26 int main(void) 27 { 28 scanf("%d",&m); 29 for(int i = 0;i < m; i++) 30 scanf("%d",&a[i]); 31 LDS(); 32 printf("%d\n",Max); 33 34 return 0; 35 }
以下兩種動態規劃方程表述方式本質上是相同的，
1 //滿足條件i>j,ai<aj && i>j,dp[i]<dp[j]+1 2 for(int j = 0;j < i;j++) 3 if(a[i] <= a[j] ) 4 dp[i] = max(dp[i],dp[j]+1); 5 6 7 8 //滿足條件i>j,ai<aj && i>j,dp[i]<dp[j]+1 9 for(int j = 0;j < i;j++) 10 if(a[i] <= a[j] && dp[i] < dp[j] + 1) 11 dp[i] = dp[j] + 1;
另一個可參考的成功AC代碼：*max_lelment(a,a+len)表示輸出集合最大元素，*min_element表示輸出集合最小元素.
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=25; 5 int dp[maxn],a[maxn]; 6 7 int main() 8 { 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++) 12 { 13 cin>>a[i]; 14 dp[i]=1; 15 } 16 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<i;j++) 19 { 20 if(a[i]<=a[j]) 21 dp[i]=max(dp[i],dp[j]+1); 22 } 23 24 cout<<*max_element(dp+1,dp+n+1); 25 return 0; 26 27 }
第三題：POJ1458 最長公共子序列
描述：
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a
subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f,
b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
輸入：
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The
input data are correct.
輸出：
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
樣例輸入：
abcfbc abfcab
programming contest
abcd mnp
樣例輸出：
4
2
0
解題分析：
字符陣列s1，s2，分別從編號1開始即不存在第0個字符，如果s1i為字符陣列s1的前i個字符構成的子串，s2j為字符陣列s2的前j個字符構成的子串，用dp[i][j]表示s1,s2的
公共子串最大長度，參考”https://blog.csdn.net/hrn1216/article/details/51534607”這篇博客的理論推導，主要考慮三種情況：
（1）i=0或j=0時最長公共子序列長度為0
（2）s1[i]=s2[j]時dp陣列的主對角線元素滿足遞推:dp[i][j]=dp[i-1][j-1]
（3）s1[i]！=s2[j]時dp陣列的副對角線元素滿足遞推:dp[i][j]=max(dp[i][j-1],dp[i-1[][j])
可用下圖來表示該程序：
*求解最長公共子序列時可以采用逆推法，但需要注意的是s1[i]!=s[j]即dp[1][j-1]=dp[i-1][j]存在分支時逆推的方向總體上要相同，要么向上要么向左，如果出現向上向左
都有則可能會導致恢復的子序列錯誤，針對上述分析給出以下關于求最長公共子序列長度的AC代碼：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define maxn 1000 5 char str1[maxn],str2[maxn]; 6 //定義兩個序列 7 int dp[maxn][maxn]; 8 //兩序列的最大公共長度 9 10 int main(void) 11 { 12 while(scanf("%s%s",str1+1,str2+1) > 0) 13 //輸入兩個序列并增加一個位元組“吃”回車 14 { 15 int length1 = strlen(str1+1); 16 int length2 = strlen(str2+1); 17 //獲取兩個序列的長度 18 for(int i = 0; i < length1; i++) 19 dp[i][0] = 0; 20 for(int j = 0 ;j < length2; j++) 21 dp[0][j] = 0; 22 //對i=0或j=0的dp數字初始化為0 23 for(int i = 1; i <= length1; i++) 24 for(int j = 1; j<= length2 ; j++) 25 if(str1[i] == str2[j]) 26 dp[i][j] = dp[i-1][j-1] + 1; 27 //當遍歷到兩字符相同時對公共長度加1 28 else 29 { 30 int m = dp[i][j-1]; 31 int n = dp[i-1][j]; 32 if(m > n) 33 dp[i][j] = m; 34 else 35 dp[i][j] = n; 36 //元素不相同時判斷副對角線上公共長度 37 } 38 printf("%d\n",dp[length1][length2]); 39 } 40 return 0; 41 }
第四題：POJ2711 合唱隊形
描述：
N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學不交換位置就能排成合唱隊形，合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1
, 2, …, K，他們的身高分別為T1, T2, …, TK，則他們的身高滿足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)，你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形，（Ti為中間點）
輸入：
輸入的第一行是一個整數N（2 <= N <= 100），表示同學的總數，第一行有n個整數，用空格分隔，第i個整數Ti（130 <= Ti <= 230）是第i位同學的身高（厘米），
輸出：
輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列，
樣例輸入
8 186 186 150 200 160 130 197 220
樣例輸出
4
解題分析：
本題由于需要求解最少需要幾個同學出列，這可以理解為求正向最大遞增子序列和最大遞減子序列這兩個序列的最大長度，遞減子序列的求解可以從后往前推即將最后一個同學認為是1，最少需要出列的人數可以采用總人數減去上述兩個序列數的和后并加1的辦法來輸出（加1是因為中間斷點計算了兩次），
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define maxn 200 5 6 int main(void) 7 { 8 int n; //同學人數 9 int a[maxn];//同學身高 10 int dp1[maxn],dp2[maxn];//記錄最長遞增、遞減子序列長度 11 scanf("%d",&n); 12 for(int i = 0; i < n; i++) 13 scanf("%d",&a[i]);//輸入身高 14 15 memset(dp1,0,sizeof(dp1));//初始化dp1 16 memset(dp2,0,sizeof(dp2));//初始化dp2 17 18 //最長遞增子序列 19 for(int i = 0; i < n; i++ ) 20 { 21 dp1[i] = 1; 22 for(int j = 0; j < i; j++) 23 if(a[i] > a[j]) 24 dp1[i] = max(dp1[i],dp1[j]+1); 25 } 26 27 //最長遞減子序列 28 for(int i = n - 1; i >= 0; i--) 29 { 30 dp2[i] = 1; 31 for(int j = n - 1; j > i; j--) 32 { 33 if(a[i] > a[j]) 34 dp2[i] = max(dp2[i],dp2[j]+1); 35 } 36 } 37 38 //求解最大值 39 int temp = 0; 40 for(int i = 0; i < n; i++) 41 if(dp1[i] + dp2[i] - 1 > temp) 42 temp = dp1[i] + dp2[i] - 1; 43 44 //輸出出列同學人數 45 printf("%d\n",n-temp); 46 47 return 0; 48 }
第五題：POJ4131 魅力手鏈
描述：
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a 'desirability' factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
輸入：
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di輸出Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
輸出：
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints.
樣例輸入：
4 6
1 4
2 6
3 12
2 7
樣例輸出：
23
解題分析：
首先對樣例進行解釋，樣例輸入第一行中4為四種項鏈，6為最大可承受的重量，第二列第二行至第五行中值為項鏈價值屬性，
該問題等價于01背包問題，即項鏈重量有限情況下選擇盡可能多的項鏈使得項鏈總價值最大化，
如果采用列舉法，每條項鏈有放入背包或不放入背包兩種可能，那么復雜度為O（2n）,顯示不可取，
如果從遞推角度考慮，對物品的重量和價值編號為W[i]，D[i]后，優先考慮第N種物品，看處理后剩下的問題是否和原問題相同并且規模可減小，
如果從動態規劃角度考慮，可以研究dp[i][j],在前i種物品中取若干種，總體積不超過j的條件下能獲得的最大價值，
如果取了第i種物品，那么則要在前i-1種物品中選取若干種，在其總體積不超過j-W[i]的條件下所能獲得的最大價值即F(i-1，j-W[i])；
如果不取第i種物品，那么問題變成了F（i-1,j）.總結來說，問題等價于當i＞1時的F(i,j)=max（F（i-1,j），F（i-1,j-W[i]）），而當i=1時有F（i,j）=D[1]（W[1] <= j）或0（W[1] > j）.
***以下為根據上述思路撰寫的程式***
這份代碼在測驗時遇到一個小插曲：主要是由于自己的粗心，下面代碼的dp[Weight_Num]處被輸成了dp[Max_Num],這導致了陣列空間開小，于是在2021年1月的某個時間POJ這道題的評測系統出現了本人的RE瘋狂刷屏，不過終于發現了這個粗心的地方，RE出現的問題有（除以0，陣列越界，指標越界，使用已經釋放的空間，陣列開得太大超出堆疊范圍），
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define Max_Num 3405 5 #define Weight_Num 12885 6 7 int main(void) 8 { 9 int n,m; 10 int W[Max_Num],D[Max_Num],dp[Weight_Num]; 11 while(scanf("%d%d",&n,&m) != EOF) 12 { 13 for(int i = 0 ; i < n; i++) 14 { 15 scanf("%d%d",&W[i],&D[i]); 16 dp[i] = 0; 17 } 18 19 //當j>=W[i]時的動規條件 20 for(int i = 0; i < n; i++) 21 { 22 for(int j = m; j >= W[i]; j--) 23 dp[j] = max(dp[j - W[i]] + D[i],dp[j]); 24 } 25 printf("%d\n",dp[m]); 26 } 27 return 0; 28 }
第六題：POJ1088 滑雪
描述:
Michael喜歡滑雪百這并不奇怪， 因為滑雪的確很刺激，可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你，Michael想知道一個區域中最長的滑坡，區域由一個二維陣列給出，陣列的每個數字代表點的高度，下面是一個例子:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小，在上面的例子中，一條可滑行的滑坡為24-17-16-1，當然25-24-23-...-3-2-1更長，事實上，這是最長的一條，
輸入:
輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)，下面是R行，每行有C個整數，代表高度h，0<=h<=10000，
輸出:
輸出最長區域的長度，
樣例輸入：
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
樣例輸出
25
對上述樣例分析：紅色路徑表示僅能走一條，綠色路徑表示能走兩條，黃色路徑表示能走三條，紫色路徑表示能走四條，高度優先為紫色>黃色>綠色>紅色，
L（2,2）=max(L(2,1),L(3,2),L(2,3),L(1,2))+1
L（2,1）=max（L（1,1），L（2,0））+1
L（1,2）=max（L（1,1），L（0,2），L（1,3））+1
L（2,3）=max（L（3,3），L（3,4））+1
L（3,2）=max（L（3,1），L（4,2））+1
.......（以此遞推）
L（0,0）=1
解題分析：
如果用L（i,j）表示從點（i,j）出發的最長滑行長度，（i,j）周圍沒有更低的點則L（i,j）=1，（i,j）周圍有更低的點則L（i,j）等于（i,j）周圍四個點高度比（i,j）低
且L值最大的點的值加1，如上述樣例的決議程序即可體現分析的思想，但是上述樣例能輸出的前提是由L（0,0）形成了倍訓，實際測驗中是無法確定L（0,0）是否為1的，這就要求
找到輸入的所有點數中高度最小的點即需要進行排序處理，在進行排序處理前應當將存盤點集合的二維陣列展開為一維陣列后進行排序，同時一維陣列又保留原來二維陣列對應的行
列下標屬性值，以便直接在一維陣列基礎上進行上述的比較處理，排序完成后，對每個點的L值初始化為1，開始按從低到高計算所有點的L，
根據以上分析可以得到以下AC代碼：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define points_num 11000 5 #define size_num 110 6 struct Point 7 { 8 int r,c; 9 int h; 10 bool operator <(const Point & p)const 11 { 12 return h < p.h;//從小到大 13 } 14 }points[points_num]; 15 //采用一維陣列存盤便于后續的排序尋找最小高度點 16 17 int a[size_num][size_num]; 18 //輸入的點矩陣 19 int dp[size_num][size_num]; 20 //關于點(i,j)的最長滑行長度 21 int row,col; 22 23 int main(void) 24 { 25 scanf("%d%d",&row,&col); 26 27 for(int i = 0; i < row; i++) 28 for(int j = 0; j < col; j++) 29 { 30 scanf("%d",&a[i][j]); 31 points[i * col + j].h = a[i][j]; 32 points[i * col + j].r = i; 33 points[i * col + j].c = j; 34 dp[i][j] = 1; 35 } 36 //一維陣列展開處理 37 38 sort(points,points + row * col); 39 //對points點集合排序 40 41 for(int i = 1; i < row * col; ++i)//從1開始是因為排序后第0個元素是最小的，這個元素的最長長度即為1 42 { 43 int r = points[i].r; 44 int c = points[i].c; 45 if(r > 0 && a[r-1][c] < a[r][c]) 46 dp[r][c] = max(dp[r-1][c] + 1,dp[r][c]); 47 if(r < row - 1 && a[r+1][c] < a[r][c]) 48 dp[r][c] = max(dp[r+1][c] + 1,dp[r][c]); 49 if(c > 0 && a[r][c-1] < a[r][c]) 50 dp[r][c] = max(dp[r][c-1] + 1,dp[r][c]); 51 if(c < col - 1 && a[r][c+1] < a[r][c]) 52 dp[r][c] = max(dp[r][c+1] + 1,dp[r][c]); 53 } 54 //以上則是判斷上下左右方向是否有路可走 55 56 int temp = 0; 57 for(int i = 0; i < row; i++) 58 for(int j = 0; j < col; j++) 59 temp = max(temp,dp[i][j]); 60 printf("%d\n",temp); 61 //輸出最大長度 62 63 return 0; 64 }
上述分析和代碼是已知最低點的最長長度通過遞推來求解最高點的最長長度，是用若干個已知狀態的值推出一個未知狀態的值，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251476.html
標籤：其他
上一篇：怎么實作軟體注冊碼功能？
下一篇：“數”的起源