线性动态规划

练习：

1. P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
2. P1020 [NOIP1999 普及组] 导弹拦截
3. P2758 编辑距离
4. P1091 [NOIP2004 提高组] 合唱队形
5. AT_dp_f LCS
6. P1140 相似基因
7. P1279 字串距离
8. P2679 子串
9. P2516 最长公共子序

---

dilworth定理

• 用最长不上升子序列覆盖整个序列，所需要的最少个数，等于最长上升序列长度
• 用最长上升子序列覆盖整个序列，所需要的最少个数，等于最长不上升序列长度

---

最长上升子序列（LIS )

[NOIP1999 提高组] 导弹拦截

#include<iostream>
using namespace std;

const int N = 1e4 + 5;
int a[N];
int dp[N];
int up[N];

int main(){
    int l = 1;
    while(cin >> a[l]){
        l++;
    }
    l--;
    for(int i = 1; i <= l; i++){
        dp[i] = 1;
        for(int j = i - 1; j >= 1; j--){
            if(a[j] >= a[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    for(int i = 1; i <= l; i++){
        up[i] = 1;
        for(int j = i - 1; j >= 1; j--){
            if(a[j] < a[i]){
                up[i] = max(up[i], up[j] + 1);
            }
        }
    }
    int ans = 0;
    int ans2 = 0;
    for(int i = 1; i <= l; i++){
        ans = max(ans, dp[i]);
        ans2 = max(ans2, up[i]);
    }
    cout << ans << endl << ans2;
    return 0;
}

B3637 最长上升子序列

#include<iostream>
using namespace std;

const int N = 5005;
int a[N];
int dp[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = 1;
        for(int j = n - 1; j >= 1; j--){
            if(a[j] < a[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

最长公共子序列（LCS）

递归dp （递归 + 备忘）dp (递推 + 填表)

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10005;
char s1[N];
char s2[N];

int lcs(int i, int j){
    if(i == 0 || j == 0) return 0;
    if(s1[i] == s2[j]) return lcs(i - 1, j - 1) + 1;
    return max(lcs(i - 1, j), lcs(i, j - 1));
}

int main(){
    cin >> (s1 + 1) >> (s2 + 1);
    cout << lcs(strlen(s1 + 1), strlen(s2 + 1));
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10005;
char s1[N];
char s2[N];
int dp[N][N];

int lcs(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 || j == 0) return dp[i][j] = 0;
    if(s1[i] == s2[j]) return dp[i][j] = lcs(i - 1, j - 1) + 1;
    return dp[i][j] = max(lcs(i - 1, j), lcs(i, j - 1));
}

int main(){
    cin >> (s1 + 1) >> (s2 + 1);
    memset(dp, -1, strlen(dp));
    cout << lcs(strlen(s1 + 1), strlen(s2 + 1));
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e4 + 5;
char s1[N];
char s2[N];
int dp[N][N];

int main(){
    cin >> (s1 + 1) >> (s2 + 1);
    int l1 = strlen(s1 + 1);
    int l2 = strlen(s2 + 1);
    for(int i = 1; i <= l2; i++){
        dp[0][i] = 0;
    }
    for(int i = 1; i <= l1; i++){
        dp[i][0] = 0;
    }
    for(int i = 1; i <= l1; i++){
        for(int j = 1; j <= l2; j++){
            if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[l1][l2];
    return 0;
}

P2758 编辑距离

#include<iostream>
#include<cstring>
using namespace std;

const int N = 2005;
char a[N];
char b[N];
int dp[N][N];

int main(){
    cin >> a + 1 >> b + 1;
    int la = strlen(a + 1);
    int lb = strlen(b + 1);
    for(int i = 1; i <= lb + 1; i++){
        dp[0][i] = i;
    }
    for(int i = 1; i <= la + 1; i++){
        dp[i][0] = i;
    }
    for(int i = 1; i <= la + 1; i++){
        for(int j = 1; j <= lb + 1; j++){
            if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; 
        }
    }
    cout << dp[la][lb];
    return 0;
}

LCS

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e4 + 5;
char s1[N];
char s2[N];
int dp[N][N];
char ans[N];

int main(){
    cin >> (s1 + 1) >> (s2 + 1);
    int l1 = strlen(s1 + 1);
    int l2 = strlen(s2 + 1);
    for(int i = 1; i <= l2; i++){
        dp[0][i] = 0;
    }
    for(int i = 1; i <= l1; i++){
        dp[i][0] = 0;
    }
    for(int i = 1; i <= l1; i++){
        for(int j = 1; j <= l2; j++){
            if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    int i = l1; 
    int j = l2;
    int idx = dp[i][j];
    while(idx > 0){
        if(s1[i] == s2[j]){ // (1)!
            ans[--idx] = s1[i];
            i--;
            j--;
        } 
        else if(dp[i][j] == dp[i - 1][j]) i--;
        else j--;
    }
    cout << ans;
    return 0;
}

1. 错误：if(dp[i][j] == dp[i - 1][j - 1] + 1)

P1140 相似基因

#include<iostream>
using namespace std;

int n, m;
const int N = 105;
char a[N];
char b[N];
int aa[N];
int bb[N];
int dp[N][N];
int xsd[6][6] = {{0}, {0, 5, -1, -2, -1, -3}, {0, -1, 5, -3, -2, -4}, {0, -2, -3, 5, -2, -2}, {0, -1, -2, -2, 5, -1}, {0, -3, -4, -2, -1, 0}};

void change_a(char a[], int n){
    for(int i = 1; i <= n; i++){
        if(a[i] == 'A') aa[i] = 1;
        else if(a[i] == 'C') aa[i] = 2;
        else if(a[i] == 'G') aa[i] = 3;
        else if(a[i] == 'T') aa[i] = 4;
        else aa[i] = 5;
    }
}

void change_b(char a[], int n){
    for(int i = 1; i <= n; i++){
        if(a[i] == 'A') bb[i] = 1;
        else if(a[i] == 'C') bb[i] = 2;
        else if(a[i] == 'G') bb[i] = 3;
        else if(a[i] == 'T') bb[i] = 4;
        else bb[i] = 5;
    }
}

int main(){
    cin >> n >> (a + 1);
    cin >> m >> (b + 1);
    change_a(a, n);
    change_b(b, m);
    for(int i = 1; i <= n; i++){
        dp[i][0] = dp[i - 1][0] + xsd[aa[i]][5];
    }
    for(int i = 1; i <= m; i++){
        dp[0][i] = dp[0][i - 1] + xsd[bb[i]][5];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = max(dp[i - 1][j - 1] + xsd[aa[i]][bb[j]], max(dp[i - 1][j] + xsd[aa[i]][5], dp[i][j - 1] + xsd[5][bb[j]]));
        } 
    }
    cout << dp[n][m];
    return 0;
}

P1091 [NOIP2004 提高组] 合唱队形

正着求（求最大值）反着求（min(求总数 - 人数)）

#include<iostream>
using namespace std;

const int N = 105;
int a[N];
int up_left[N];
int up_right[N];
int n;
void f1(){
    for(int i = 1; i <= n; i++){
        up_left[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[j] < a[i]){
                up_left[i] = max(up_left[i], up_left[j] + 1);
            }
        }
    }
}

void f2(){
    for(int i = n; i >= 1; i--){
        up_right[i] = 1;
        for(int j = n; j > i; j--){
            if(a[j] < a[i]){
                up_right[i] = max(up_right[i], up_right[j] + 1);
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    f1();
    f2();
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, up_left[i] + up_right[i] - 1);//i(当前枚举的分界线)被重复计算 
    }
    cout <<  n - ans;
    return 0;
}

#include<iostream>
using namespace std;

const int N = 105;
int a[N];
int up_left[N];
int up_right[N];
int n;
void f1(){
    for(int i = 1; i <= n; i++){
        up_left[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[j] < a[i]){
                up_left[i] = max(up_left[i], up_left[j] + 1);
            }
        }
//      cout << up_left[i] << " ";
    }
    for(int i = 1; i <= n; i++){
        up_left[i] = i - up_left[i];
    }
}

void f2(){
    for(int i = n; i >= 1; i--){
        up_right[i] = 1;
        for(int j = n; j > i; j--){
            if(a[j] < a[i]){
                up_right[i] = max(up_right[i], up_right[j] + 1);
            }
        }
//      cout << up_right[i] << " ";
    }
    for(int i = 1; i <= n; i++){
        up_right[i] = (n - i + 1) - up_right[i];
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    f1();
    f2();
    int ans = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        ans = min(ans, up_left[i] + up_right[i]);
    }
    cout << ans;
    return 0;
}