聲明

最近博主身體不適，更新較慢，請大家體諒體諒

最大上升子序列

【題目描述】
一個數的序列
你的任務，就是對于給定的序列，求出最大上升子序列和。注意，最長的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和為100，而最長上升子序列為(1,2,3)。

【輸入】
輸入的第一行是序列的長度N(1≤N≤1000)。第二行給出序列中的N個整數，這些整數的取值范圍都在0到10000(可能重復)。

【輸出】
最大上升子序列和。

如果前面的最長上升子序列那道題理解清楚了，那么該題做起來就會發現本質上和前一道題是一樣的。該題的決策對象和階段都和前一道題一樣，只是狀態變為dp[i]表示以第i個數作為結尾的最大上升子序列的長度。
決策：這里要求子序列之和最大，對于每一個位置的數，只能從前面的比當前值小的數轉移過來，要求序列之和最大，那么這個序列前面選擇的數之和要最大，那么我們需要從前面可以選擇的點中序列和最大的點轉移過來。

我們設dp[i]表示以i結尾的最大子序列之和，那么我們就可以很輕松的得到一下內容
$$dp[i]=max(dp[i],dp[j]+a[i])j\in [1,i?1]$$
所以就有以下ACcode

#include<bits/stdc++.h>
using namespace std;int a[10010],dp[10010],ans=INT_MIN;
int main(){int n;cin>>n;for (int i=1;i<=n;i++){cin>>a[i];dp[i]=a[i];}	for (int i=1;i<=n;i++){for (int j=1;j<i;j++){if (a[j]<a[i]){dp[i]=max(dp[i],dp[j]+a[i]);}}ans=max(ans,dp[i]);}cout<<ans;return 0;
}

合唱隊形

我們先來看一道例題

[NOIP2004 提高組] 合唱隊形

題目描述

$n$ 位同學站成一排，音樂老師要請其中的 $n?k$ 位同學出列，使得剩下的 $k$ 位同學排成合唱隊形。

合唱隊形是指這樣的一種隊形：設 $k$ 位同學從左到右依次編號為 $1,2,$ … $,k$，他們的身高分別為 $t_1,t_2,$ … $,t_k$，則他們的身高滿足 $t_1<?<t_i>t_{i+1}>$ … $>t_k(1\le i\le k)$。

你的任務是，已知所有 $n$ 位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

輸入格式

共二行。

第一行是一個整數 $n$（$2\le n\le 100$），表示同學的總數。

第二行有 $n$ 個整數，用空格分隔，第 $i$ 個整數 $t_i$（$130\le t_i\le 230$）是第 $i$ 位同學的身高（厘米）。

輸出格式

一個整數，最少需要幾位同學出列。

樣例 #1

樣例輸入 #1

8
186 186 150 200 160 130 197 220

樣例輸出 #1

4

提示

對于 $50\%$ 的數據，保證有 $n\le 20$。

對于全部的數據，保證有 $n\le 100$。

該題實際上就是前面求一個最長上升子序列，對后面求一個最長下降子序列。但是問題在于這兩個序列的連接點我們不知道，沒有辦法直接求解出來，也就是說任意一個點都有可能作為這個連接點，所以我們需要先枚舉這個連接點x，再分別對區間[1,x]求最長上升子序列，對區間[x+1,n]求最長下降子序列。這種做法的時間復雜度為O(n³),但是該題的數據范圍改為n<=2000,所以還需要優化。

我們先看前面的最長上升子序列，在枚舉的連接點i逐漸增大的時候，如果我們已經存儲了前i-1個數的最長上升子序列的答案，那么前i個數的最長上升子序列的答案就只有兩種情況，第一種就是前面i-1的答案，第二種就是以第i個點作為結尾的答案，沒有必要再去前面重新計算一次，每一次的時間復雜度為O(n)。對于后面的下降序列，在i增大時，范圍在逐漸縮小，我們只需要把它看做是增大就可以，這種做法在之前做過的一些題中使用過，我們只需要倒著枚舉連接點i即可，這樣，i在逐漸變小，后面的區間在增大，做法和前面一樣。

#include<bits/stdc++.h>
using namespace std;int n,dp1[5000],dp2[5000];//dp1為從前往后的最長上升子序列，dp2為從后往前 
int a[5000],minn=INT_MAX;
int main(){cin>>n;for (int i=1;i<=n;i++){cin>>a[i];dp1[i]=1;dp2[i]=1;}for (int i=1;i<=n;i++){for (int j=1;j<i;j++){if (a[j]<a[i]){dp1[i]=max(dp1[i],dp1[j]+1);}}}for (int i=n;i>=1;i--){for (int j=n;j>i;j--){if (a[i]>a[j]){dp2[i]=max(dp2[i],dp2[j]+1);}}}for (int i=n;i>=1;i--){minn=min(n-dp1[i]-dp2[i],minn);}cout<<minn+1;return 0;
}

最長公共子序列

我們要得到兩個字符串的最長公共子序列，暴力做法是先枚舉一個字符串的開頭，再去枚舉另一個字符串的開頭，然后找出最大公共子列，時間復雜度為O(n^3)。我們考慮如何優化，前面依然是枚舉兩個字符串的開頭，主要考慮求最大公共子序列時是否可以通過前面算出的答案直接得到正確答案。考慮開頭無法知道匹配的最長公共子序列到底匹配到了哪一個位置，所以我們記錄下以當前位置結尾的最長公共序列的長度。因為有兩個字符串，所以dp[i]無法分別記錄兩個字符串的結尾位置，所以需要用dp[i][j]。

狀態：我們設dp[i][j]表示前綴長度為i的a子串和一個長度為j的b序列的最長公共子序列的長度。決策對象：每個位置的字符。階段：a串的每個位置和b串的每個位置都可以組合，一共有n*m個階段。決策：如果a[i]==b[j]，那么(i,j)相對于(i1,j-1)會多匹配一個，即dp[i][j]=dp[i-1][j-1]。如果a[i]!=b[j]，答案就是dp[i-1][j-1]嗎？其實并不是，因為a[i]可以和b[j-1]匹配，或者b[j]可以和a[i-1]匹配，這種情況下，dp[i-1][j-1]的答案是錯誤的。

當a[i]!=b[j]時，正確答案是dp[i][j]=max (dp[i-1][j],dp[i][j-1])，那么萬一是a[i]和b[j1]、a[i-1]和b[j]都無法匹配的情況，是否還需要和dp[i-1][j-1]比較呢？不需要，因為在這種情況下，計算dp[i][j-1]時，a[i]!=b[j-1]，那么dp[i][j-1]=max(dp[i-1][j-1], dp[i][j-2])，這個答案中已經報了dp[i-1][j-1]的情況，所以不需要再和dp[i-1][j-1]比較。還需要設置初始值，當a串和b串都沒有字符時，最長公共串長度為1，即dp[0][0]=0。

#include<bits/stdc++.h>
using namespace std;int dp[1010][1010];
int main(){string a,b;cin>>a>>b;dp[0][0]=0;for (int i=1;i<=a.length();i++){for (int j=1;j<=b.length();j++){if (a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[a.length()][b.length()];return 0;
}

最長公共子串

該題和上一題的狀態、對象、階段都是相同的，不同的是狀態的轉移。dp[i][j]表示以位置i結尾的a串和以位置j結尾的b串的最長公共子串. 如果a[i]!=b[j]，那么這個子串一定是不可以匹配的，因為這里說了分別以i,j結尾，所以dp[i][j]=0。如果a[i]=b[j],長度就在之前的dp[i-1][j-1]的基礎上增加1，即dp[i][j]=dp[i-1][j-1]+1。

#include<bits/stdc++.h>
using namespace std;int dp[1500][1510];
int maxn=INT_MIN;
int main(){string a,b;cin>>a>>b;dp[0][0]=0;for (int i=1;i<=a.length();i++){for (int j=1;j<=b.length();j++){if (a[i-1]==b[j-1]){dp[i][j]=dp[i-1][j-1]+1;}maxn=max(dp[i][j],maxn);}}cout<<maxn;return 0;
}