Zhiming's Blog

第三道算法题：多米诺骨牌

题目：

小高最近迷上了玩多米诺骨牌：沿直线将一长串排摆放起来，推倒一个引起连锁反应，非常有趣。现在有 n 块牌，每张牌都有各自的高度和宽度(分别记为 $h_i$ 和 $w_i$ )。小高的摆放规则是，后面的牌的高度和宽度必须都大于前面的牌，请问小高用这n张牌最多能选出多少张组成一个最长牌阵呢？

输入描述：

第一行一个整数n

接下来n行，每行两个整数 $h_i$ 和 $w_i$ .（所有牌中没有长度相同或者宽度相同的两张牌）

输出描述：

一个数X，表示最多能选出X张组成最长牌列

样例输入：

5

5 5

3 1

2 6

4 2

1 4

样例输出：
3 （第一张牌：3 1，第二张牌：4 2，第三张牌：5 5）

思路：（动态规划）

请注意题目要求，题目要求的是长度和宽度都必须大于前面的牌，且所有的长宽都没有相同的！所以，我们只需要排序一组，比如排序长度，那么，我们在长度的排序列表中是不是找到一个最长的关于宽度的连续子序列，是不是就是最优解呢？
这是一个最长上升子序列的经典问题，一般的解法有两种，一种是动态规划算法，复杂度是O( $n^2$ )的；另外一种是基于二分查找，复杂度是O( $nlogn$ )。
在这里，我们会将两种解法的代码都贴出来。（面鲸大大说这是一道送分题，回过头来看确实😂当时太菜了）

代码（动态规划）：By Python

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 读取第一行输入
n =int(input())

# 读取第二行开始的n行输入
for i in n:
    h[i],w[i] = map(int,input().split(' '))
print(h,w)
 
# 定义完美字符串的长度变量
maxLength = 0

# 遍历26个字母，并匹配完美字符串的字母 
for i in range(26):
    # 定义左指针（完美字符串的起点）和容错（可替换的字母个数）
    left, faultTolerant = 0,0
    # 定义一个右指针（完美字符串的终点），右指针大小从0到母字符串的长度
    for right in range(n):
        # 当且仅当右指针指向的字母的ASCII码 不等于 第一个for循环指定的字母的ASCII码
        if ord(s[right]) != ord('a') + i:
            # 因为右指针不等于当前for循环的26个字母中之一，所以容错加1
            faultTolerant += 1
        #如果容错大于了输入给定的最大容错m，这个时候没办法了，就只能动左指针了（右移）
        while faultTolerant > m:
            # 存在着一种情况，左指针目前匹配的刚好是for循环指定的字母的ASCII码，此情况就不能减少容错
            # 如果左指针当前匹配不是for指定的字母的ASCII码，那么右移左指针不就可以减少容错了吗？
            if ord(s[left]) != ord('a') + i:
                faultTolerant -= 1
            # 注意缩进，如果在if循环中，意味着只有当左指针不匹配ACSII码，左指针才+1，显然不符合逻辑
            left += 1
        # 注意缩进
        maxLength = max(maxLength, right-left+1)
print(maxLength)

第四道算法题

题目：

据说是最难的一道题，当然我没有写。不过不影响我去研究他，希望可以吃透！

在n（1 $\leq$ n$\leq $35）个正整数中，任意挑选k个（不可重复挑选，0$ \leq $k$ \leq$n）数字的和记为sum，另有一个正整数m，请问sum%m的最大值是多少？

输入描述：

第一行两个整数，分别是n和m

第二行为n个正整数

输出描述：

一个数x，x表示sum%m的最大值

样例输入：

5 5

1 2 3 4 5

样例输出：

4

思路