#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()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;

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


    int ma=-1;
    //状态转移
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        f[i][j]=0;
        if(a[i]!=b[j])
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
        else f[i][j]=f[i-1][j-1]+1;

        if(ma<f[i][j])
         ma=f[i][j];
    }

    cout<<ma;

    return 0;
}

#include<iostream>

using namespace std;

const int N=1010;
int n,a[N],f[N];

int main()
{
    cin>>n;

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

    f[1]=1;
    //状态转移方程
    int ma=1;
    for(int i=2;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
             f[i]=max(f[i],f[j]+1);
        }
        if(ma<f[i])
          ma=f[i];
    }

    cout<<ma<<endl;
    return 0;
}

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


using namespace std;

const int N = 505;
int n,a[N][N];


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

    for(int i=n;i>=1;i--)
     for(int j=i;j>=1;j--)
     a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];

    cout<<a[1][1]<<endl;

    return 0;
}

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


using namespace std;

const int N = 505;
int n,a[N][N];


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

    for(int i=n;i>=1;i--)
     for(int j=i;j>=1;j--)
     a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];

    cout<<a[1][1]<<endl;

    return 0;
}

//图论复习
const int N = 100, M = 2 * N;
//树和无权图的存储
int h[N], e[M], ne[M], idx; //前插法建立链表

void add(int a, int b) { //添加一条a->b的无权边
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

//树和无权图的dfs
bool vis[N];//全局数组默认值为0

void dfs(int u) {
    vis[u] = true; //只遍历一遍

    //遍历边
    for (int i = h[a]; i != -1; i = ne[i]) {
        int j = e[i] //取顶点,i代表的是下标
                dfs(j);
    }
}

//广度优先遍历
queue<int> q;
void bfs(int u) {
    q.push(u);
    vis[u] = true;
    int x;
    while (q.size()) {
        x = q.front();
        q.pop();

        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!vis[j]) {
                vis[j] = true; //标记为访问过
                q.push(j);
            }

        }
    }
}

//拓扑排序

//数组模拟队列
int que[N], hh = 0, tt = -1; //hh 是队头 tt 是队尾

//队列有 front size empty push pop 操作

//向队尾插入一个数
q[++tt] = x; //x为插入的元素

hh++;//队首出去

q[hh];//队首的值

int size = tt - hh + 1; //个数

//判断是否为空 队列中是否含有元素
if (hh <= tt) {

}


//数组模拟栈
int sta[N], tt = 0;

sta[++tt] = x //x是压入栈的元素
            sta[tt];//栈顶的值
tt--;//弹出栈

//判断栈是否为空
if (tt > 0) {

}


int d[N];//存放入度
bool topsort() { //判断是否存在拓扑序列(图中是否有环)
    //模拟队列
    int hh = 0, tt = -1, q[N];

    //找到入度为0的点 删去顶点其所有的边,重复此过程
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;

    while (hh <= tt) { //队列不为空
        int t = q[hh++]; //取队列首元素，并且队首出去

        //删除所有顶点
        for (int i = h[t]; i != -1; i = ne[i]) { //i为顶点的下标
            int j = e[i]; //取出边
            if (--d[j] == 0) //删除点并且判断度是否为0，重复
                q[++tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

//有权图
W[M];//区别在于多了个权值
void add(int a, int b, int c) { //多了c为权值
    e[idx] = b;
    ne[idx] = h[a];
    W[idx] = c;
    h[a] = idx++;
}

//基本跟无权图一样

//最小生成树


//要使用并查集，防止产生环
int ds[N];//并查集数组

int n, m; //n为顶点数，m为边数
//边集结构体
struct edge {
    int a, b, w;

    //小于运算符重载
    bool operator <(const edge &x)const {
        return w < x.w;
    }

} eg[N];
bool vis[N];

int find(int x) { //查找父节点
    if (ds[x] != x)
        ds[x] = find(ds[x]); //优化
    return ds[x];
}

int kruskal() {
    //思想：贪心，贪边，每次扩展最小权值的边，要判断是否产生环直到遍及整个图
    sort(eg, eg + m); //边排序

    //初始化并查集
    for (int i = 0; i < n; i++)
        ds[i] = i;

    int res = 0, cnt = 0; //res为生成树代价,cnt为连接顶点数

    for (int i = 0; i < m; i++) {
        //获取边的信息
        int a = eg[i].a, b = eg[i].b, w = eg[i].w;

        a = find(a), b = find(b);
        if (a != b) { //防止产生环
            ds[a] = b;
            res += w;
            cnt++;
        }
    }

    //判断是否成功

    if (cnt < n - 1)
        return -1;
    return res;
}


typedef pair<int, int> PII;
#define x first
#define y second
//最短路径
int dist[N];//存储该点到其他点的距离
bool st[N]; //判断该点到其他点的距离是否确定
int dijkstra() {
    //前提性质：最短路径的任何连续子序列都为最短路径
    //算法思想: 确定入选边集，找到最小边，对已经入选边的顶点，更新入选边集
    //重复此过程
    memset(dist, 0x3f, sizeof dist); //设置距离为无穷

    dist[1] = 0; //到自己的距离为0

    //堆申请
    priority_queue<PII, vector<PII>, greater<PII>> heap; //PII默认参数
    heap.push({0, 1}); //first为存储距离,second 为点的编号

    //更新入选边集
    while (heap.size()) {
        auto t = heap.top();
        int distance = t.x, ver = t.y; //提取编号和距离

        if (st[ver])
            continue;//如果该点最短距离已经确定，跳出
        st[ver] = true;

        //正式更新边集
        for (int i = h[ver]; i != -1; i = ne[i]) { //读取边正常操作,i为顶点下标
            int j = e[i];
            //判断是否更新
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                //堆只能删除堆顶的元素
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[N] == 0x3f)
        return -1;
    else
        return dist[N];
}

//二维数组存
int g[N][N];
bool vis[N];

//深度优先遍历
void dfs(int u) {
    vis[u] = true;

    for (int i = 0; i < n; i++)
        if (g[u][i] && !vis[i])
            dfs(i);

}

//广度优先遍历

void bfs(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = 0; i < n; i++)
            if (g[u][i] && !vis[i]) {
                vis[i] = true;
                q.push(i);
            }
    }
}


//拓扑排序

bool topsort() {
    //模拟队列
    int q[N], hh = 0, tt = -1;

    //找到度为0的结点
    for (int i = 0; i < n; i++)
        if (!d[i])
            q[++tt] = i;

    //删除相关边，再重复

    while (hh <= tt) {
        //出队列
        int t = q[hh++];

        for (int i = 0; i < n; i++)
            if (g[t][i])
                if (--d[i] == 0)
                    q[++tt] = i;
    }
}

int main() {
    //图的初始化
    idx = 0;
    memset(h, -1, sizeof(h)); //邻接表和二维数组都一样 memset(g,-1,sizeof(g));

    return 0;
}

                                       基础算法复习
1.前缀和
const int N=1e5+10;
//前缀和,目的：快速求出数组中某段区间和

//一维前缀和
int a[N];//原数组
int s[N];//前缀和数组

//边界处理(全局数组不用)
s[0]=0;

//目的：快速求出数组中某段区间和
s[r]=s[l-1]//求出[l,r]中的和

//构造
s[i]=s[i-1]+a[i];


//二维前缀和,目的：求出在二维数组中的某个矩形（或正方形）的区域内数字之和
int a[N][N];
int s[N][N];//注意下标统一从(1,1)开始



//边界处理 s[0][j],s[0][0],s[i][0]都为0
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];  //从(1,1)到(i,j)的区域内数字和

//求区域(x1,y1)到(x2,y2)内数字之和为
S=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][x2-1];//减1是因为包含边界

                            算法比赛数据结构复习
//基本数据结构练习
#include<iostream>

using namespace std;

const int N = 1e5 + 10;

//算法比赛中数据结构使用
//数组
int a[N];

//队列模拟
int q[N], int hh = 0, tt = -1;//hh为队首，tt为队尾

int size = hh - tt+1;//队列元素个数
q[++tt]=x;//在队尾插入一个元素
hh++;//队首弹出一个元素

//用例
while (hh <= tt)
{
    int t = q[hh++];//取队首元素并且弹出
}


//栈模拟
int s[N], top = 0;

int size = top;//元素个数

s[top++];//压栈
top--;//弹栈
s[top];//取栈顶元素

//用例
while (top > 0)
{
    int t = s[top--];//取栈顶并且弹栈
}

//单链表模拟
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N],val[N],idx;

void init()
{
    idx = 0;
    head = -1;
}

void add(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

//将头结点删除
void remove()
{
    head = ne[head];
}

//图
const int M = 2*N;
//无权图
int h[N], e[M], ne[N], idx;

void  add(int a, int b)//添加一条a到b的边
{
    e[idx] = h[a];
    ne[idx] = b;
    h[a] = idx++;
}

//有权图
int h[N], e[M], ne[M], W[M], idx;

void add(int a, int b, int c)//添加一条a到b的权值为c的边
{
    e[idx] = h[a];
    ne[idx] = b;
    W[idx] = c;
    h[a] = idx++;
}


int main()
{
    //图的初始化
    idx = 0;
    memset(h, -1, sizeof(h));
}


//不经常用的并查集
//并查集
int Max = 1005;
int pa[Max]; int rank[Max]

void init(int n) 
{
    for (int i = 0; i < n; i++) 
    {
        pa[i] = i;
        rank[i] = 1;
    }
}//初始化

//朴素版
int Find(int n) 
{
    if (pa[n] = n)
        return n;
    else Find(pa[n]);//它自己不是代表结点
}//查找
void Union(int m, int n) 
{
    pa[Find(n)] = Find(m);//集合m和n合并
}//合并

//优化,路径压缩
int find(int n) 
{
    if (pa[n] = n)
        return n;
    else {
        pa[n] = find(pa[n]);//保存的为根结点
    }
}
void u_nion(int m, int n) {
    int rm = find[m], rn = find(n);
    if (rank[rm] > rank[rn])
    {
        pa[rn] = rm;
    }
    else pa[rm] = rn;
    if (rm != rn && rank[rm] = rank[rn])
        rank[rn]++;
}

总结：
一.目前学习的算法和思想:
  1.基础算法:
   排序：
   二分：
   前缀和和差分：
   双指针:
   位运算:
   区间合并:
   离散化:
  2.数据结构：
   单双链表
   栈和队列
   单调栈和单调队列
   并查集
   数和图
  3.搜索：
   bfs和dfs
  4.图论：
   图的遍历:bfs和dfs
   图的拓扑排序
   图的最小生成树：kruskal算法,prime算法
   图上两点的最短路径: 单源最短路径dijkstra 所有点对:floyd 两点之间的最短路径:bfs搜索
  5.其他算法思想
   暴力
   DP
   贪心
  6.其他:
   基本语法和c++STL使用

                                     STL复习

#include<vector>
//vector 动态可变长数组 学习
    //声明
    vector<int> a;
    vector<int> b[150];//创建了包含150元素的数组，每个元素是一个vector容器,相当于矩阵
    struct zbg
    {
        int x, y;
    };
    vector<zbg> c;//结构体vector
    //插入和删除
    a.push_back(5);//尾插
    a.pop_back();//尾删
    //元素的提取
    a.front();//首元素
    a.back();//尾元素
    //元素大小和判空
    a.size();
    a.empty();
    //迭代器
    vector<int>::iterator first = a.begin(), last = a.end();
    //获得a的首尾迭代器
    a.clear();//清空a的所有元素

#include<stack>
//栈 stack
    stack<int> sta;
    //基本
    sta.size(); sta.empty();

    //插入删除
    sta.push(1);//入栈
    sta.pop();//出栈
    sta.top();//栈顶元素引用


#include<queue>
//queue和priority_queue  队列  学习
    //声明
    queue<int> q;
    //插入和删除
    q.push(2);//入队咧
    q.pop();//出队列
    //元素提取
    q.front(); q.back();
    //基本
    q.empty(); q.size();

    //优先级队列学习 priority_queue 二叉堆 默认为大根堆
    //声明
    priority_queue<int> z;
    priority_queue<zbg> z1;//结构体要重载小于运算符
    struct zbg
    {
        int x, y;
        bool operator <(const zbg &a)const
        {
            return this.x<a.x;
        }
    };
    priority_queue<pair<int, string>> z2;//二元组优先级队列
    //插入和删除
    z.push(5);//堆插入
    z.pop();//只能删除堆顶
    //元素提取
    z.top();
    z.size(); z.empty();//基本函数

    //大根堆转换成小根堆
    //1.正整数和正小数转换为负数存储(不推荐)
    //2.创建结构体，对小于运算符重载
    struct Int {
        int x;
        Int(const int& a) : x(a) {}
        bool operator<(const Int& a)
        {
            return x > a.x;
        }
    };
    priority_queue<Int> z0;//int类型的小根堆


//pair  二元组  学习
    pair<string, int> min;//带默认值的初始化
    pair<string, int> max("zbg", 1);//赋初始值
    min = make_pair("zbg", 1);//调用函数初始化,make_pair生成一个pair临时对象
    min.first; min.second;//元素获取,数据成员，不是函数
    //比较运算符
    min == max;//当且仅当两个分别相等
    min < max;//小于运算 只比较第一个

#include<deque>
//双端队列学习  deque 两端都有口
    deque<int> j;
    //插入和删除
    j.push_back(1);//尾插
    j.pop_back();//尾删
    j.push_front(3);//头插
    j.pop_front();//头删
    //特殊功能
    j[0];//下标运算符类似数组
    //基本
    j.size(); j.empty(); j.clear();
    //迭代器
    typename deque<int>::iterator deque_first = j.begin(), deque_last = j.end();


#include<set>
//有序非重复集合  set 和有序重复集合 multiset  底层实现为红黑树，会自动排序
    //声明
    set<int> s; multiset<int> ms;
    //自定义结构体时候要重载小于运算符
    //基本
    s.size(); s.empty(); s.clear();
    ms.size(); ms.empty(); ms.clear();

    //中序迭代器 只提供了前++ 和前--的操作(双向访问迭代器，只能左右不能随机)
    typename set<int>::iterator set_first = s.begin(), set_last = s.end();
    --set_first; ++set_first;

     //插入和删除
    s.insert(1); s.erase(s.begin());
    ms.insert(1); ms.erase(s.begin());
    s.erase(s.begin());//删除，元素和迭代器都可以,元素会删除全部，迭代器只是一个

    //其他特殊函数
    s.find(2);//查找函数,返回迭代器
    s.lower_bound(2);//查找>=2的最小的一个，返回迭代器
    s.upper_bound(2);//查找>2的最小的一个，返回迭代器
    s.count(2);//返回s中元素2的个数


#include<map>
//映射<key,value>的二元映射 map和multimap 前者不允许重复，后者可以 底层是红黑树
    //声明,常用做(伪)哈希表
    map<int, int> ma;//自定义结构体要重载小于运算符

    //基本
    ma.size(); ma.empty(); ma.clear();
    ma.begin(); ma.end();//双向迭代器,begin,end仍是前闭后开的范围

    //迭代器 返回值是二元组pair
    typename map<int, int>::iterator map_first = ma.begin();

    //插入和删除
    pair<int, int> mac(5, 1);
    ma.insert(mac); ma.insert(make_pair(5, 2));//插入参数为pair二元组
    ma.erase(ma.begin());

    //其他操作
    ma.find(5);//返回迭代器
    //索引运算符重载
    ma[5] = 3;//对关键码5进行改写，没有就创建
    //也可以直接查找


#include<unordered_map>
//哈希表 unordered_map 底层是哈希表实现
    //声明
    unordered_map<string, int> hash;
    //基本跟map差不多
    hash.insert(make_pair("zbg", 1));
    hash.insert(pair<string, int>("npc", 1));//隐式转换
    hash.insert(unordered_map<string, int>::value_type("npc", 1));//非隐式转换
    hash.erase(hash.end());


#include<algorithm>
//STL算法学习

//algorithm容器算法内容，以vector为例
    vector<int> wj;
    reverse(wj.begin(), wj.end());//容器翻转
    unique(wj.begin(), wj.end());//去重,返回尾指针
    //运用，求个数
    int n = wj.end() - unique(wj.begin(), wj.end());
    random_shuffle(wj.begin(), wj.end());//随机打乱,用法跟reverse相同
    next_permutation(wj.begin(), wj.end());//求字典序下一个排列，并且直接在原容器上更新，不存在就返回false

    sort(wj.begin(), wj.end());//排序函数
    //排序结构体时需要重载小于运算符或者自定义比较函数
    bool cmp(int a, int b)
    {
        return a < b;
    }
    sort(wj.begin(), wj.end(), cmp);
    //下面两个函数都返回元素位置迭代器
    lower_bound(wj.begin(), wj.end(), 5);//二分查找第一个大于等于5的元素
    upper_bound(wj.begin(), wj.end(), 5);//二分查找第一个大于5的元素

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


using namespace std;

typedef pair<int, int> PII;
const int N = 2e5;

int n, m;
//图的存储
int h[N], e[N], ne[N], w[N], idx;

int dis[N];//点到其他点的距离
bool vis[N];//点是否距离确定
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra() {
    //贪心，每次扩展边集，每次取最短的
    memset(dis, 0x3f, sizeof(dis));

    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆申请
    heap.push({0, 1});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int distance = t.first, ver = t.second;

        if (vis[ver])
            continue;
        vis[ver] = true;

        //扩展边集
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];

            //比较距离
            if (dis[j] > distance + w[i]) {
                dis[j] = distance + w[i];

                heap.push({dis[j], j}); //更新边集
            }

        }
    }

    if (dis[n] == 0x3f3f3f3f)
        return -1;

    return dis[n];
}


int main() {
    idx = 0;
    memset(h, -1, sizeof(h));

    cin >> n >> m;
    int x, y, z;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        add(x, y, z);
    }

    cout << dijkstra() << endl;
    return 0;
}

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


using namespace std;

typedef pair<int, int> PII;
const int N = 2e5;

int n, m;
//图的存储
int h[N], e[N], ne[N], w[N], idx;

int dis[N];//点到其他点的距离
bool vis[N];//点是否距离确定
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra() {
    //贪心，每次扩展边集，每次取最短的
    memset(dis, 0x3f, sizeof(dis));

    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆申请
    heap.push({0, 1});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int distance = t.first, ver = t.second;

        if (vis[ver])
            continue;
        vis[ver] = true;

        //扩展边集
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];

            //比较距离
            if (dis[j] > distance + w[i]) {
                dis[j] = distance + w[i];

                heap.push({dis[j], j}); //更新边集
            }

        }
    }

    if (dis[n] == 0x3f3f3f3f)
        return -1;

    return dis[n];
}


int main() {
    idx = 0;
    memset(h, -1, sizeof(h));

    cin >> n >> m;
    int x, y, z;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        add(x, y, z);
    }

    cout << dijkstra() << endl;
    return 0;
}