#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] +  1);
        }

    cout << f[n][m] << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int q[N];// 所有不同长度上升序列结尾的最小值

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];

    int len = 0;
    for (int i = 0; i < n; i ++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r  + 1>> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

// dp   状态表示 f[i]
//          集合：所有以第i个数结尾的上升子序列
//          属性：max
//      状态计算
//          集合划分 f[i]
//              倒数第二个数是a[j](j = 0, 1, 2, 3,...,i - 1)

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, f[i]);

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

// Dp  状态表示
//          集合：所有从起点到(i, j)的路径
//          属性：max
//     状态计算
//          集合划分            f[i, j] 
//                      来自左上       来自右上
//               f[i-1,j-1]+a[i,j]   f[i-1,j]+a[i,j]
using namespace std;

const int N = 510, INF = 1e9;

int g[N][N];
int f[N][N];
int n;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= i; j ++)
            scanf("%d", &g[i][j]);

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= i + 1; j ++)
            f[i][j] = -INF;

    f[1][1] = g[1][1];
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + g[i][j], f[i - 1][j] + g[i][j]);

    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++){
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= 0; j --)
            for (int k = 0; k < s[i]; k ++)
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2010;

int n, V;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> V;

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;

    for (int i = 1; i <= n; i ++)
        for (int j = V; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, V;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> V;

    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= V; j ++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);

    cout << f[n][V] << endl;

    return 0;
}

朴素版本

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, V;
int w[N], v[N];
int f[N][N];

int main()
{
    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 ++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][V] << endl;

    return 0;
}

优化版本

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, V;
int w[N], v[N];
int f[N];

int main()
{
    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 = v[i]; j <= V; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V] << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

// 在背包装得下时，背包内总物品的价值最高是多少？
// 1、0 1背包问题：每件物品最多只能用一次
// 2、完全背包问题：每件物品无限次使用
// 3、多重背包问题：每个物品最多有si个
//      -- 优化版
// 4、分组背包问题：有N组物品 限制条件

// Dp —— 状态表示 f(i,j) —— 集合：所有只考虑前i个物品，且体积不超过j的集合
//                       —— 属性：集合当中每个方案的最大价值
//    —— 状态计算 —— 集合划分 选不选第i个物品(不重不漏)
//                       —— 所有不选第i个物品的方案
//                       —— 所有选择第i个物品的方案
using namespace std;

const int N = 1010;

int n, V;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> V;

    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; // 输入体积和价值

    for (int i = 1; i <= n; i ++)// i是前ige物品
        for (int j = V; j >= v[i]; j --)// j是枚举的体积
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V];


    return 0;
}