【算法训练营】最长公共子序列，倒水问题，奶牛吃草（Python实现）

5
1 2 4 3 5
5 2 3 4 1

2

代码实现 

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 件事中的任意一件：

1. 用水龙头装满一个杯子。
2. 倒空一个杯子。
3. 把一个杯子里的水倒到另一个杯子里，直到一个杯子空了或者另一个杯子满了。
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 10
1
9
11
19

44

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)