LCS(Longest Common Subsequence)最長公共子序列。給定兩個序列a和b，當另一序列c即是a的子序列又是b的子序列時，稱c時a和b的公共子序列，最長公共子序列時所有子序列中長度最長的。
注意子序列是在原序列中删去若幹元素後得到的序列，注意子序列≠子串，子串在原序列中是連續的。
HDU-1159 Common Subsequence
Problem Description
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 a text file. Each data set in the file 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.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
char a[maxn], b[maxn];
int dp[maxn][maxn];
int main() {
while (~scanf("%s%s", a + , b + )) {
memset(dp, , sizeof(dp));
int len1 = strlen(a + );
int len2 = strlen(b + );
for (int i = ; i <= len1; i++)
for (int j = ; j <= len2; j++)
if (a[i] == b[j])dp[i][j] = dp[i - ][j - ] + ;
else dp[i][j] = max(dp[i][j - ], dp[i - ][j]);
printf("%d\n", dp[len1][len2]);
}
return ;
}
//滾動數組版後文有
複制
| high[] | d[] | len |
|---|---|---|
| 1 5 6 2 3 4 | 1 | 1 |
| 1 5 6 2 3 4 | 1 5 | 2 |
| 1 5 6 2 3 4 | 1 5 6 | 3 |
| 1 5 6 2 3 4 | 1 2 6 | 3 |
| 1 5 6 2 3 4 | 1 2 3 | 3 |
| 1 5 6 2 3 4 | 1 2 3 4 | 4 |
結束後len=4，即LIS長度為4。
HDU-1257 最少攔截系統
Problem Description
某國為了防禦敵國的飛彈襲擊,發展出一種飛彈攔截系統.但是這種飛彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以後每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的飛彈來襲.由于該系統還在試用階段,是以隻有一套系統,是以有可能不能攔截所有的飛彈.
怎麼辦呢?多搞幾套系統呗!你說說倒蠻容易,成本呢?成本是個大問題啊.是以俺就到這裡來求救了,請幫助計算一下最少需要多少套攔截系統.
Input
輸入若幹組資料.每組資料包括:飛彈總個數(正整數),飛彈依此飛來的高度(雷達給出的高度資料是不大于30000的正整數,用空格分隔)
Output
對應每組資料輸出攔截所有飛彈最少要配備多少套這種飛彈攔截系統.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int n, high[maxn];
int LIS1() { //法一
int high2[maxn],dp[][maxn] = { };//滾動數組
memcpy(high2, high, sizeof(high));
sort(high2 + , high2 + n + );
for (int i = ; i <= n; i++) //LCS
for (int j = ; j <= n; j++)
if (high[i] == high2[j])
dp[i & ][j] = dp[i & ? : ][j - ] + ;
else
dp[i & ][j] = max(dp[i & ? : ][j], dp[i & ][j - ]);
return dp[n&][n];
}
int LIS2() { //法二
int dp[maxn], ans = ;
for (int i = ; i <= n; i++) {
dp[i] = ;
for (int j = ; j < i; j++)
if (high[j] < high[i])
dp[i] = max(dp[j] + , dp[i]);
ans = max(ans, dp[i]);
}
return ans;
}
int LIS3() { //法三
int d[maxn], len = ;
d[] = high[];
for (int i = ; i <= n; i++)
if (high[i] > d[len])
d[++len] = high[i];
else { //用lower_bound()查詢第一個>high[i]的位址
int j = lower_bound(d + , d + len + , high[i]) - d;
d[j] = high[i];
}
return len;
}
int main() {
while (cin>>n) {
for (int i = ; i <= n; i++)
cin >> high[i];
//cout << LIS1() << "\n";
//cout << LIS2() << "\n";
cout << LIS3() << "\n";
}
return ;
} 複制
原創不易，請勿轉載（本不富裕的通路量雪上加霜 ）
部落客首頁：https://blog.csdn.net/qq_45034708