最长公共子序列
时间限制：1 sec
空间限制：256 MB
问题描述
给定两个 1 到 n 的排列 A,B （即长度为 n 的序列，其中 [1,n] 之间的所有数都出现了恰好一次）。
求它们的最长公共子序列长度。
输入格式
第一行一个整数 n ，意义见题目描述。
第二行 n 个用空格隔开的正整数 A[1],…,A[n]，描述排列 A。
第三行 n 个用空格隔开的正整数 B[1],…,B[n]，描述排列 B。
输出格式
一行一个整数，表示 A,B 的最长公共子序列的长度。
样例输入
5
1 2 4 3 5
5 2 3 4 1
样例输出
2
样例解释
(2,3) 和 (2,4) 都可以是这两个序列的最长公共子序列。
数据范围
对于 80% 的数据，保证 n<=5,000。
对于 100% 的数据，保证 n<=50,000。
提示
[把 A 中的所有数替换成其在 B 中出现的位置，想一想，新序列的最长上升子序列和所求的东西有什么关系呢？]
代码实现
def cal_loc():
for i in range(1, n + 1):
loc[b[i]] = i
def lis():
a[1] = b[1]
k = 1
for i in range(2, n + 1):
if a[k] < b[i]:
k += 1
a[k] = b[i]
else:
l, r = 1, k
while l <= r:
mid = (l + r) // 2
if a[mid] < b[i]:
l = mid + 1
else:
r = mid - 1
a[l] = b[i]
return k
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
loc = [0] * (n + 1)
cal_loc()
for i in range(1, n + 1):
b[i] = loc[a[i]]
print(lis())倒水问题
时间限制：10 sec
空间限制：256 MB
问题描述
邓老师有有 2 个容量分别为 n 单位、m 单位的没有刻度的杯子。初始，它们都是空的。
邓老师给了你 t 分钟时间。每一分钟，他都可以做下面 4 件事中的任意一件：
- 用水龙头装满一个杯子。
- 倒空一个杯子。
- 把一个杯子里的水倒到另一个杯子里，直到一个杯子空了或者另一个杯子满了。
- 什么都不做。
邓老师希望最后能获得 d 个单位的水，假设最后两个杯具中水量的总和为 x，那么邓老师的不满意度就为 |d-x|。
你希望邓老师尽可能地满意，于是请你计算邓老师的不满意度最小是多少。
输入格式
一行 4 个整数 n,m,t,d，分别表示两个杯具的容量、时间限制、以及邓老师的期望值。
输出格式
一行一个整数，表示邓老师最小的不满意度。
样例输入
7 25 2 16
样例输出
9
样例解释
你可以在第 1 分钟用水龙头装满任意一个杯子，并在第 2 分钟什么都不做，即可让邓老师的不满意度为 9。
可以证明不存在更优的解。
数据范围
本题共设置 16 个测试点。
对于前 1 个测试点，保证 t=1。
对于前 2 个测试点，保证 t<=2。
对于前 4 个测试点，保证 t<=4。
对于前 10 个测试点，保证 1<=n,m<=100，1<=t<=100，1<=d<=200。
对于所有的 16 个测试点，保证 1<=n,m<=2,000，1<=t<=200，1<=d<=4,000。
代码实现
奶牛吃草
时间限制：4 sec
空间限制：256 MB
问题描述
有一只奶牛在一条笔直的道路上（可以看做是一个数轴）。初始，它在道路上坐标为 K 的地方。
这条道路上有 n 棵非常新鲜的青草（编号从 1 开始）。其中第 i 棵青草位于道路上坐标为 x[i] 的地方。贝西每秒钟可以沿着道路的方向向前（坐标加）或向后（坐标减）移动一个坐标单位的距离。
它只要移动到青草所在的地方，就可以一口吞掉青草，它的食速很快，吃草的时间可以不计。
它要吃光所有的青草。不过，青草太新鲜了，在被吞掉之前，暴露在道路上的每棵青草每秒种都会损失一单位的口感。
请你帮它计算，该怎样来回跑动，才能在口感损失之和最小的情况下吃掉所有的青草。
输入格式
第一行两个用空格隔开的整数 n,k，分别表示青草的数目和奶牛的初始坐标。
第 2 行到第 n+1 行，第 i+1 行有一个整数 x[i]，描述第 i 棵青草的坐标。
输出格式
一行一个整数，表示吃掉所有青草的前提下，最小损失的口感之和。保证答案在 32 位有符号整数的范围内。
样例输入
4 10
1
9
11
19
样例输出
44
样例解释
先跑到 9，然后跑到 11，再跑到 19，最后到 1，可以让损失的口感总和为 29+1+3+11=44。可以证明不存在比这更优的解。
数据范围
对于 50% 的数据，保证 1≤n≤4，1≤k,x[i]≤20。 对于 80% 的数据，保证 1≤n≤100。 对于 100% 的数据，保证 1≤n≤1000，1≤k,x[i]≤10^6。
提示
[我们先从另一个角度看答案，即损失的总口感：从初始状态到奶牛吃掉第 1 棵草之间的时间（我们在下面把它叫做第 1 段时间），所有的 n 棵青草都在流失口感；……；从奶牛吃掉第 i 棵草到它吃掉第 i+1 棵草之间的时间（我们在下面把它叫做第 i+1 段时间），还没有被吃掉的 n-i 棵草都在流失口感；……]
[于是我们发现，第 i 段时间对答案的贡献，为这段时间的长度与 n-i+1 的乘积。]
[接着，我们再来关注最优策略。吃完一棵草后（包括初始时），奶牛的最优策略一定是直奔另一棵草。]
[由于奶牛不会飞，所以奶牛走过的所有路一定是一段连续的区间。]
[显然地，被奶牛经过过的地方，按最优策略，一定不会留下青草。]
[所以我们可以**将所有青草的坐标排序**（下面我们都使用排完序后的编号），然后用 dp[l][r][j] 表示吃完 [l,r] 范围内的青草时的最小答案，j 只有 0,1 两种取值，分别表示奶牛吃完最后一棵草停在青草 l 还是 r 上（只有可能是这两种情况，否则与上面的结论矛盾）。]
[于是我们就可以轻易地设计出状态转移方程：]
[dp[l][r][0]=min(dp[l+1][r][0]+(n-r+l)*abs(x[l]-x[l+1]),dp[l+1][r][1]+(n-r+l)*abs(x[l]-x[r]))]
[dp[l][r][1]=min(dp[l][r-1][1]+(n-r+l)*abs(x[r]-x[r-1]),dp[l][r-1][0]+(n-r+l)*abs(x[r]-x[l]))]
[边界为：dp[i][i][j]=abs(x[i]-k)*n（对于所有1<=i<=n，j=0,1）]
[友情提示：请注意枚举顺序。]
代码实现
def min_taste_loss(n, k, x):
INF = float('inf')
dp = [[[INF for _ in range(2)] for _ in range(n + 1)] for _ in range(n + 1)]
# Base case
for i in range(1, n + 1):
dp[i][i][0] = dp[i][i][1] = abs(x[i] - k) * n
# Dynamic programming
for length in range(2, n + 1):
for l in range(1, n - length + 2):
r = l + length - 1
dp[l][r][0] = min(dp[l + 1][r][0] + (n - r + l) * abs(x[l] - x[l + 1]),
dp[l + 1][r][1] + (n - r + l) * abs(x[l] - x[r]))
dp[l][r][1] = min(dp[l][r - 1][1] + (n - r + l) * abs(x[r] - x[r - 1]),
dp[l][r - 1][0] + (n - r + l) * abs(x[r] - x[l]))
return min(dp[1][n][0], dp[1][n][1])
# 读取输入
n, k = map(int, input().split())
x = [0] + [int(input()) for _ in range(n)] # 青草的坐标，下标从1开始
# 排序青草的坐标
x.sort()
# 输出结果
result = min_taste_loss(n, k, x)
print(result)