首页 ACM

最长上升子序列

给定一个长度为 NN 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 NN。

第二行包含 NN 个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N≤10001≤N≤1000,
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

AC代码

#include <bits/stdc++.h>
using namespace std;

int a[1005];
int dp[1005];

int main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    int cnt = -1;
    for (int i = 0; i < N; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[i] > a[j] && dp[j] + 1 > dp[i]) {
                // 重点:从这个点开始找前缀,看是否能做这个点的前缀,再看能否使序列变得更长
                dp[i] = dp[j] + 1;
            }
        }
        cnt = max(cnt, dp[i]);
    }
    cout << cnt << endl;
}

最长公共子序列

给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB,求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含一个长度为 NN 的字符串,表示字符串 AA。

第三行包含一个长度为 MM 的字符串,表示字符串 BB。

字符串均由小写字母构成。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N,M≤10001≤N,M≤1000

输入样例:

4 5
acbd
abedc

输出样例:

3

AC代码

#include <bits/stdc++.h>
using namespace std;

const int ma = 1005;
int N, M;
char A[ma], B[ma];
int dp[ma][ma];

int main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) 
    {
        cin >> A[i];
    }
    for (int i = 1; i <= M; ++i) 
    {
        cin >> B[i];
    }
    for (int i = 1; i <= N; ++i) 
    {
        for (int j = 1; j <= M; ++j) 
        {
            if (A[i] == B[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[N][M] << endl;
}

01背包

有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vivi,价值是 wiwi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,VN,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 NN 行,每行两个整数 vi,wivi,wi,用空格隔开,分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

8

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1005;
int dp[MAX][MAX];
int v[MAX];
int w[MAX];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) 
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= N; ++i) 
    {
        for (int j = 0; j <= V; ++j) 
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) 
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    int maxn = 0;
    for (int i = 0; i <= V; ++i) 
    {
        maxn = max(maxn, dp[N][i]);
    }
    cout << maxn << endl;
    return 0;
}



文章评论

目录