題目鏈接：

https://vjudge.net/problem/UVA-12511

---

題目大意：

給定兩個(gè)序列，求出兩個(gè)序列的最長(zhǎng)公共上升子序列（嚴(yán)格上升）。

---

解題過程：

比賽的時(shí)候沒有做出來，非常咸魚的一場(chǎng)比賽，當(dāng)時(shí)是想錯(cuò)了狀態(tài)。當(dāng)時(shí)想的狀態(tài)是定義dp[i][j]，意味以第一個(gè)串第前i個(gè)元素，第二個(gè)串前j個(gè)元素的最長(zhǎng)公共上升子序列長(zhǎng)度。

但是這樣定義狀態(tài)有后效性，比如當(dāng)前我知道dp[i][j]要以這個(gè)狀態(tài)進(jìn)行轉(zhuǎn)移的話，需要他是以那個(gè)狀態(tài)轉(zhuǎn)移而來的，換句話說，我轉(zhuǎn)移的時(shí)候要知道他是以前j個(gè)數(shù)中那一個(gè)結(jié)尾的。

如果換一種方式，dp[i][j]代表以第一個(gè)序列前i個(gè)元素并且以第i個(gè)結(jié)束，第二個(gè)序列前j個(gè)元素并且以第j個(gè)元素結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度。

這樣加入的限制太多，不容易找出狀態(tài)轉(zhuǎn)移方程，或者轉(zhuǎn)移起來太麻煩。

---

題目分析：

這里以dp[i][j]表示第一個(gè)序列中前i個(gè)元素，第二個(gè)序列前j個(gè)元素并且以第j個(gè)元素為結(jié)尾的最長(zhǎng)上升子序列。

這樣對(duì)比前兩種狀態(tài)表示方式有兩種好處，一是無后效性，dp[i][j]的第二維就確定了這個(gè)序列是以那一個(gè)元素結(jié)尾。二是容易進(jìn)行轉(zhuǎn)移，對(duì)于dp[i][j]可由兩種方式轉(zhuǎn)移而來：

dp[i][j]={dp[i?1][j],max(dp[i?1][k])+1,a[i]≠b[i]k∈[1,j?1]∧b[k]<b[j]∧a[i]=b[i]

這里的k可以在循環(huán)中找出，時(shí)間復(fù)雜度為O(n2).

---

AC代碼：

#include <bits/stdc++.h> using namespace std;const int MAX = 1123;int dp[MAX][MAX], a[MAX], b[MAX];int main() {int T;scanf("%d", &T);while (T--) {int n, m;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d", &b[i]);}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++) {int maxn = 0;for (int j = 1; j <= m; j++) {//不相等時(shí)的轉(zhuǎn)移dp[i][j] = dp[i-1][j];//更新maxn變量，表示當(dāng)前小于a[i]的dp[i-1][k]的最大值if (a[i] > b[j] && maxn < dp[i-1][j])maxn = dp[i-1][j];//相等的話if (a[i] == b[j])dp[i][j] = maxn+1;}}int ans = 0;for (int i = 1; i <= m; i++) {ans = max(ans, dp[n][i]);}printf("%d\n", ans);} }

轉(zhuǎn)載于:https://www.cnblogs.com/ACMFish/p/7222830.html

總結(jié)

以上是生活随笔為你收集整理的UVA12511 - Virus（DP+最长公共上升子序列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。