头像

皓首不倦




在线 



皓首不倦
21小时前




'''
枚举B1所有约数,然后验证约数和b0的最小公倍数是不是b1, 以及和a0的最大公约数是不是a1
枚举约数时候用dfs枚举质因数的次幂的组合方案的方式进行
'''



def get_prime(N):
    prime_vals = []
    flag = [True] * (N+1)
    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)

        for p_val in prime_vals:
            if val * p_val > N:
                break

            flag[val * p_val] = False

            if val % p_val == 0:
                break

    return prime_vals

primes = get_prime(100000)


# 分解质因数函数,返回元组数组[ (质因子1, 次幂1), (质因子2, 次幂2), (质因子3, 次幂3) ...... ]
# 质因子的数值升序排列
def devide_prime(val):
    ans = []

    for i in primes:
        if i*i > val:
            break

        if val % i == 0:
            cnt = 0
            while val % i == 0:
                val //= i
                cnt += 1

            ans.append((i, cnt))

        if val == 1:
            break

    # 特判最后可能剩下的大于sqrt(val)的最大的质因子
    if val != 1:
        ans.append((val, 1))

    return ans

# 获取所有约数的函数
def get_approximate_numbers(val):
    ans = []
    primes = devide_prime(val)

    def dfs(idx, prev_val):
        if prev_val*prev_val > val:
            return

        if idx >= len(primes):
            ans.append(prev_val)
            if val // prev_val != prev_val:
                ans.append(val // prev_val)

            return

        base = None
        for pow_val in range(primes[idx][1]+1):
            if pow_val == 0:
                base = 1
            else:
                base *= primes[idx][0]

            dfs(idx+1, prev_val * base)
    dfs(0, 1)

    return ans

def gcd(a, b):
    if a > b:
        a, b, = b, a

    while a:
        a, b = b % a, a
    return b


n = int(input())
for _ in range(n):
    a0, a1, b0, b1 = map(int, input().split())
    app_vals = get_approximate_numbers(b1)

    cnt = 0
    for app_val in app_vals:
        if b0 * app_val == b1 * gcd(app_val, b0):
            if gcd(app_val, a0) == a1:
                cnt += 1

    print(cnt)





活动打卡代码 AcWing 1053. 修复DNA



# import sys
# sys.stdin = open("data.txt", "r")


'''
基于AC自动机的DP
'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
    def __init__(self, fa):
        self.s = ''             # end节点自己本身的单词
        self.fail_s = []        # fail指针指向的节点序列的单词列表(如果fail指针指向的节点是一个end节点,此字段保存所有这些单词的列表)
        self.next = {}          # 边和子节点映射
        self.is_end = False     # 是否是end节点
        self.fail = None        # ac自动机的fail指针
        self.fa = fa            # 父节点指针
        self.id = 0             # 节点的id号

class AcTrie:
    def __init__(self):
        self.root = AcTrieNode(None)
        self.__idx = 1

    def append(self, s: str):
        cur = self.root
        for ch in s:
            if ch not in cur.next:
                new_node = AcTrieNode(cur)
                new_node.id = self.__idx
                self.__idx += 1

                new_node.s = cur.s + ch
                cur.next[ch] = new_node

            cur = cur.next[ch]
        cur.is_end = True

    # 构建ac自动机接口
    def build(self, s_list = []):
        # 第一步是构建普通的Trie
        for s in s_list:
            self.append(s)

        # 层次遍历构建Fail指针
        que = deque()
        que.append(self.root)

        depth = 0
        while len(que) > 0:
            node_num = len(que)

            for _ in range(node_num):
                cur = que.popleft()
                if depth == 1:
                    # 根节点下面的第一层word长度是1,是没有后缀的,fail指针全部指向root
                    cur.fail = self.root
                elif depth != 0:
                    cur.fail = self.root

                    # 循环找最长后缀的候选
                    p = cur.fa.fail
                    last_ch = cur.s[-1]
                    while True:
                        if not p:
                            break

                        if last_ch in p.next:
                            cur.fail = p.next[last_ch]

                            f = cur.fail
                            if f.is_end:
                                # 如果fail指针指向的节点是一个end节点,或者这个节点的fail_s列表不为空,需要添加这些单词到cur节点的fail_s列表中
                                cur.fail_s.append(f.s)

                            # fail指针指向的节点中fail_s里面的单词必须全部继承下来,因为这些单词也是后缀的备选
                            for s in f.fail_s:
                                cur.fail_s.append(s)

                            break
                        else:
                            p = p.fail

                for new_node in cur.next.values():
                    que.append(new_node)

            depth += 1

    # 获取节点状态转移的表 [0号点转移表,1号点转移表, ......]
    def get_stat_map(self):
        ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

        def dfs(node: AcTrieNode):
            for ch in 'AGCT':
                if ch in node.next:
                    if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
                        # 发生了匹配,下一个字符不可能是ch
                        ans[node.id][ch] = None
                    else:
                        ans[node.id][ch] = node.next[ch].id

                else:
                    cur = node
                    while True:
                        if ch in cur.next:
                            if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
                                # 发生了匹配,下一个字符不可能是ch
                                ans[node.id][ch] = None
                            else:
                                ans[node.id][ch] = cur.next[ch].id

                            break

                        else:
                            if cur.fail is not None:
                                cur = cur.fail
                            else:
                                ans[node.id][ch] = cur.id
                                break

            for child in node.next.values():
                dfs(child)

        dfs(self.root)
        return ans

case_id = 1
while True:
    n = int(input())
    if n == 0:
        break

    ac_trie = AcTrie()

    for _ in range(n):
        ac_trie.append(input())

    ac_trie.build()
    stat_map = ac_trie.get_stat_map()

    s = input().strip()
    cache = [[None]*(len(s)+1) for _ in range(20*n)]
    n = len(s)

    # dp(stat, ii)表示Ac自动机状态为stat情况下,继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
    def dp(stat, ii):
        if ii == n:
            return 0

        if cache[stat][ii] is not None:
            return cache[stat][ii]

        ans = 0x7fffffff
        for ch in 'AGCT':
            if stat_map[stat][ch] is None:
                continue

            t = 0
            if s[ii] != ch:
                t += 1

            t += dp(stat_map[stat][ch], ii+1)
            ans = min(ans, t)

        # print(stat, ii, ans, n)
        cache[stat][ii] = ans
        return ans

    ans = dp(ac_trie.root.id, 0)
    print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
    case_id += 1







# import sys
# sys.stdin = open("data.txt", "r")


'''
基于AC自动机的DP
'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
    def __init__(self, fa):
        self.s = ''             
        self.fail_s = []        
        self.next = {}          
        self.is_end = False     
        self.fail = None        
        self.fa = fa            
        self.id = 0             

class AcTrie:
    def __init__(self):
        self.root = AcTrieNode(None)
        self.__idx = 1

    def append(self, s: str):
        cur = self.root
        for ch in s:
            if ch not in cur.next:
                new_node = AcTrieNode(cur)
                new_node.id = self.__idx
                self.__idx += 1

                new_node.s = cur.s + ch
                cur.next[ch] = new_node

            cur = cur.next[ch]
        cur.is_end = True

    def build(self, s_list = []):
        for s in s_list:
            self.append(s)

        que = deque()
        que.append(self.root)

        depth = 0
        while len(que) > 0:
            node_num = len(que)

            for _ in range(node_num):
                cur = que.popleft()
                if depth == 1:
                    cur.fail = self.root
                elif depth != 0:
                    cur.fail = self.root

                    p = cur.fa.fail
                    last_ch = cur.s[-1]
                    while True:
                        if not p:
                            break

                        if last_ch in p.next:
                            cur.fail = p.next[last_ch]

                            f = cur.fail
                            if f.is_end:
                                cur.fail_s.append(f.s)

                            for s in f.fail_s:
                                cur.fail_s.append(s)

                            break
                        else:
                            p = p.fail

                for new_node in cur.next.values():
                    que.append(new_node)

            depth += 1

    # 获取节点状态转移的表 [0号点转移表,1号点转移表, ......]
    def get_stat_map(self):
        ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

        def dfs(node: AcTrieNode):
            for ch in 'AGCT':
                if ch in node.next:
                    if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
                        # 发生了匹配,下一个字符不可能是ch
                        ans[node.id][ch] = None
                    else:
                        ans[node.id][ch] = node.next[ch].id

                else:
                    cur = node
                    while True:
                        if ch in cur.next:
                            if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
                                # 发生了匹配,下一个字符不可能是ch
                                ans[node.id][ch] = None
                            else:
                                ans[node.id][ch] = cur.next[ch].id

                            break

                        else:
                            if cur.fail is not None:
                                cur = cur.fail
                            else:
                                ans[node.id][ch] = cur.id
                                break

            for child in node.next.values():
                dfs(child)

        dfs(self.root)
        return ans

case_id = 1
while True:
    n = int(input())
    if n == 0:
        break

    ac_trie = AcTrie()

    for _ in range(n):
        ac_trie.append(input())

    ac_trie.build()
    stat_map = ac_trie.get_stat_map()

    s = input().strip()
    cache = [[None]*(len(s)+1) for _ in range(20*n)]
    n = len(s)

    # dp(stat, ii)表示Ac自动机状态为stat情况下,继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
    def dp(stat, ii):
        if ii == n:
            return 0

        if cache[stat][ii] is not None:
            return cache[stat][ii]

        ans = 0x7fffffff
        for ch in 'AGCT':
            if stat_map[stat][ch] is None:
                continue

            t = 0
            if s[ii] != ch:
                t += 1

            t += dp(stat_map[stat][ch], ii+1)
            ans = min(ans, t)

        # print(stat, ii, ans, n)
        cache[stat][ii] = ans
        return ans

    ans = dp(ac_trie.root.id, 0)
    print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
    case_id += 1









import sys





'''
S(i) 表示开始工作时间小于等于i的雇佣员工的总数
需要满足的差分约束:
1. S(i) >= S(i-1) (i=1,2,3,4,....23)
2. S(0) >= 0

对于i >= 0 and i <= 8 而言
3. S(i) + S(23) - S(i+16) >= arr[i]
对于i >= 9 and i <= 23 而言
3. S(i) - S(i-8) >= arr[i]

4. S(i) - S(i-1) <= cnt[i], cnt[i]是从i时间开始工作的人的数量

从0到1000枚举S(23), 如果有一个S(23)能够让差分系统的最小解 小于等于 申请人的数量
就找到了一组可行解,找最小的S(23)即是答案

'''


from collections import Counter
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getInfo(min_path=True)

    # 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMaxPathLen(self):
        return self.getInfo(min_path=False)

    # min_path表示求的是最短路径还是最长路径
    def getInfo(self, min_path = True):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if (min_path == True and w < 0) and (min_path == False and w > 0):
                    # 有正环或者负环提前退出
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:

                    if dis[a] == 0x7fffffff:
                        if w == -0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = 0x7fffffff

                    elif dis[a] == -0x7fffffff:
                        if w == 0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = -0x7fffffff
                    else:
                        new_dis = dis[a] + w


                    if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
                        dis[b] = new_dis
                        update_flag = True

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return [[node, dis[node]] for node in range(1, self.max_node_num+1)]



t = int(input())
for _ in range(t):
    arr = list( map(int, input().split()) )
    n = int(input())
    possible = [0] * 24
    for i in range(n):
        possible[int(input())] += 1

    if sum(possible) == 0:
        print(0)
    else:
        find_ans = False
        min_cost = 0x7fffffff
        for S23 in range(0, n+1):
            # 为了方便计算,所有数值下标都往后移动了一个位置, 超级源点已定义为23, 实际存储时候用24的位置
            edges = []

            # S(i) >= S(i-1) (i=1,2,3,4,....22)
            for i in range(1, 23):
                edges.append((i-1+1, i+1, 0))

            # S(22) <= S(23)
            edges.append((24, 22+1, 0))

            # S(i) >= S(i+16) - S23 + arr[i]
            for i in range(8):
                edges.append((i+16+1, i+1, arr[i]-S23))

            # S(i) >= S(i-8) + arr[i]
            for i in range(8, 23):
                edges.append((i-8+1, i+1, arr[i]))

            # S(23) - S(15) >= arr[23], S(15) <= S(23) - arr[23]
            edges.append((15+1, 24, -(S23 - arr[23])))

            # S(0) <= possible[0]
            edges.append((0+1, 24, -possible[0]))

            # S(i) - S(i-1) <= possible[i] i = 1, 2, 3..... 22
            for i in range(1, 23):
                edges.append((i+1, i-1+1, -possible[i]))

            # S(23) - S(22) <= possible[23] => S(22) >= S(23) - possible[23]
            edges.append((24, 22+1, S23 - possible[23]))


            # 虚拟源点向所有点添加边 S(i) >= 0, i = 0, 1, 2, ..... 22
            for i in range(23):
                edges.append((24, i+1, 0))

            algo = SPFA(24, edges, is_directed=True, max_node_num=24)
            ans = algo.getMaxPathLen()
            if ans is None:
                continue

            find_ans = True
            min_cost = min(min_cost, S23)

        if find_ans:
            print(min_cost)
        else:
            print('No Solution')







import sys

'''
将1号节点固定在0位置,构造超级源点建图,单源最短路求最大解,如果图里面有负环,则无解
如果最大解最后一个数值能够到0x7ffffffe, 则最前面和最后面的奶牛之间的距离可以无穷大
剩下的情况就是正常的查分约束的解
'''

from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getInfo(min_path=True)

    # 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMaxPathLen(self):
        return self.getInfo(min_path=False)

    # min_path表示求的是最短路径还是最长路径
    def getInfo(self, min_path = True):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if (min_path == True and w < 0) and (min_path == False and w > 0):
                    # 有正环或者负环提前退出
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        cnt = [0] * (self.max_node_num + 1)
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:
                    if dis[a] == 0x7fffffff:
                        if w == -0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = 0x7fffffff

                    elif dis[a] == -0x7fffffff:
                        if w == 0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = -0x7fffffff
                    else:
                        new_dis = dis[a] + w


                    if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
                        dis[b] = new_dis
                        cnt[b] = cnt[a] + 1
                        update_flag = True

                        if cnt[b] >= self.max_node_num:
                            return None

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return dis

edges = []
n, m1, m2 = map(int, input().split())
for i in range(m1):
    a, b, w = map(int, input().split())
    if a > b:
        a, b = b, a

    # val(b) - val(a) <= w
    edges.append((a, b, w))

for i in range(m2):
    a, b, w = map(int, input().split())
    if a > b:
        a, b = b, a

    # val(b) - val(a) >= w
    edges.append((b, a, -w))


for i in range(2, n+1):
    # 后一个要大于等于前一个
    # val(i) >= val(i-1)
    edges.append((i, i-1, 0))

    # 从2开始的每一个点都小于等于一个极大值,这样才能让超级源点对每一个点都是可达的,注意这里不能取0x7fffffff, 这个数值表示的是不可达
    edges.append((n+1, i, 0x7ffffffe))

# 超级源点是n+1, 要求1号点固定在0位置
edges.append((1, n+1, 0))
edges.append((n+1, 1, 0))


# print(edges)
algo = SPFA(n+1, edges, is_directed=True, max_node_num=n+1)
ans = algo.getMinPathLen()
if ans is None:
    print(-1)
else:
    if ans[n] == 0x7ffffffe:
        print(-2)
    else:
        print(ans[n])



活动打卡代码 AcWing 900. 整数划分

cache = [[None]* 1005 for _ in range(1005)]

# dp(i, j)表示用小于等于j的数凑i的所有方案的数量
def dp(i, j):
    if i == 0:
        return 1

    if j == 1:
        return 1

    if cache[i][j] is not None:
        return cache[i][j]

    if j > i:
        ans = dp(i, i)
    else:
        ans = dp(i-j, j) + dp(i, j-1)

    cache[i][j] = ans % 1000000007
    return ans % 1000000007

n = int(input())
print(dp(n, n))



活动打卡代码 AcWing 899. 编辑距离



#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int cache[11][11];


char ss[1005][12];
char s[12];


char *s1 = nullptr, *s2 = nullptr;

// dp(i, j)表示将A前i个字符变为B前j个字符的最少变换次数
int dp(int i, int j) {
    if (i == -1) {
        return j + 1;
    }

    if (j == -1) {
        return i + 1;
    }

    if (cache[i][j] != -1) {
        return cache[i][j];
    }

    int ans = 0x7fffffff;
    ans = min(ans, dp(i, j-1) + 1);     // 最后一次是加字符
    ans = min(ans, dp(i-1, j) + 1);     // 最后一次是删字符

    // 最后一次是修改字符
    if (s1[i] == s2[j]) {
        ans = min(ans, dp(i-1, j-1));
    } else {
        ans = min(ans, dp(i-1, j-1) + 1);
    }

    cache[i][j] = ans;
    return ans;
}


int get_dis(char* ss1, char* ss2) {
    memset(cache, -1, sizeof(cache));
    s1 = ss1, s2 = ss2;
    int ans = dp(strlen(s1)-1, strlen(s2)-1);

    return ans;
}


int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
    int n, m, limit;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", ss[i]);
    }

    for (int k = 0; k < m; k++) {
        scanf("%s %d", s, &limit);

        int tot = 0;
        for (int i = 0; i < n; i++) {
            if (get_dis(ss[i], s) <= limit) {
                tot++;
            }
        }
        printf("%d\n", tot);
    }

    return 0;

}


活动打卡代码 AcWing 902. 最短编辑距离

import sys

# sys.stdin = open("input.txt", "r")


sys.setrecursionlimit(5000000)

n1 = int(input())
s1 = input()
n2 = int(input())
s2 = input()

cache = [[-1] * 1005 for _ in range(1005)]


# 将A前i个字符转换为B前j个字符的最小变换次数
def dp(i, j):
    if cache[i][j] != -1:
        return cache[i][j]

    if i == -1:
        # A添加j+1个字符
        return j + 1

    if j == -1:
        # A删掉i+1个字符
        return i + 1

    ans = 0x7fffffff
    ans = min(ans, dp(i, j - 1) + 1)  # 最后一次是添加字符
    ans = min(ans, dp(i - 1, j) + 1)  # 最后一次是删除字符

    # 最后一次是修改字符
    if s1[i] == s2[j]:
        ans = min(ans, dp(i - 1, j - 1))
    else:
        ans = min(ans, 1 + dp(i - 1, j - 1))

    cache[i][j] = ans
    return ans


print(dp(len(s1) - 1, len(s2) - 1))






# import sys
# sys.stdin = open("input.txt", "r")


N = 100005

# x[len]表示当前已经找到的长度是len的严格上升子序列的最小结尾数值
x = [0x7fffffff] * N

# dp[i]表示以i位置结尾的最长严格上升子序列的长度
dp = [1] * N

n = int(input())
arr = list(map(int, input().split()))

cur_len = 1     # 当前已经找到的最长上升子序列最长长度
ans = 1
x[1] = arr[0]

for i in range(1, n):
    l, r = 1, cur_len
    while l <= r:
        mid = (l + r) // 2
        if x[mid] < arr[i]:
            dp[i] = mid + 1
            l = mid + 1
        else:
            r = mid - 1

    x[dp[i]] = min(x[dp[i]], arr[i])
    if dp[i] == cur_len+1:
        cur_len += 1

    ans = max(ans, dp[i])

print(ans)



活动打卡代码 AcWing 901. 滑雪


import sys
# sys.stdin = open("input.txt", "r")


m, n = map(int, input().split())
g = []

for i in range(m):
    g.append(list(map(int, input().split())))

cache = [[-1] * 305 for _ in range(305)]

# dp(i, j) 表示从(i, j)位置触发的所有合法方案中,最多的区域的个数
def dp(i, j):
    if cache[i][j] != -1:
        return cache[i][j]

    ans = 1
    for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if ii >= 0 and ii < m and jj >= 0 and jj < n and g[ii][jj] < g[i][j]:
            ans = max(ans, 1 + dp(ii, jj))

    cache[i][j] = ans
    return ans


ans = 1
for i in range(m):
    for j in range(n):
        ans = max(ans, dp(i, j))

print(ans)