动态规划-LCS、LIS

#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 ;
}
//滚动数组版后文有

#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 ;
}