网站开发最新技术,福州网站建设制作首选荧光信息,高端品牌网站建设兴田德润实力强,做网站页面对PS切图最长公共子序列 时间限制#xff1a;1 sec 空间限制#xff1a;256 MB 问题描述 给定两个 1 到 n 的排列 A,B #xff08;即长度为 n 的序列#xff0c;其中 [1,n] 之间的所有数都出现了恰好一次#xff09;。 求它们的最长公共子序列长度。 输入格式 第一行一个整数 n 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% 的数据保证 n5,000。 对于 100% 的数据保证 n50,000。 提示 [把 A 中的所有数替换成其在 B 中出现的位置想一想新序列的最长上升子序列和所求的东西有什么关系呢] 代码实现 def cal_loc():for i in range(1, n 1):loc[b[i]] idef lis():a[1] b[1]k 1for i in range(2, n 1):if a[k] b[i]:k 1a[k] b[i]else:l, r 1, kwhile l r:mid (l r) // 2if a[mid] b[i]:l mid 1else:r mid - 1a[l] b[i]return kn 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 个测试点保证 t1。
对于前 2 个测试点保证 t2。
对于前 4 个测试点保证 t4。
对于前 10 个测试点保证 1n,m1001t1001d200。
对于所有的 16 个测试点保证 1n,m2,0001t2001d4,000。
代码实现 奶牛吃草 时间限制4 sec 空间限制256 MB 问题描述 有一只奶牛在一条笔直的道路上可以看做是一个数轴。初始它在道路上坐标为 K 的地方。 这条道路上有 n 棵非常新鲜的青草编号从 1 开始。其中第 i 棵青草位于道路上坐标为 x[i] 的地方。贝西每秒钟可以沿着道路的方向向前坐标加或向后坐标减移动一个坐标单位的距离。 它只要移动到青草所在的地方就可以一口吞掉青草它的食速很快吃草的时间可以不计。 它要吃光所有的青草。不过青草太新鲜了在被吞掉之前暴露在道路上的每棵青草每秒种都会损失一单位的口感。 请你帮它计算该怎样来回跑动才能在口感损失之和最小的情况下吃掉所有的青草。 输入格式 第一行两个用空格隔开的整数 n,k分别表示青草的数目和奶牛的初始坐标。 第 2 行到第 n1 行第 i1 行有一个整数 x[i]描述第 i 棵青草的坐标。 输出格式 一行一个整数表示吃掉所有青草的前提下最小损失的口感之和。保证答案在 32 位有符号整数的范围内。 样例输入 4 10
1
9
11
19样例输出 44样例解释 先跑到 9然后跑到 11再跑到 19最后到 1可以让损失的口感总和为 29131144。可以证明不存在比这更优的解。 数据范围 对于 50% 的数据保证 1≤n≤41≤k,x[i]≤20。 对于 80% 的数据保证 1≤n≤100。 对于 100% 的数据保证 1≤n≤10001≤k,x[i]≤10^6。 提示 [我们先从另一个角度看答案即损失的总口感从初始状态到奶牛吃掉第 1 棵草之间的时间我们在下面把它叫做第 1 段时间所有的 n 棵青草都在流失口感……从奶牛吃掉第 i 棵草到它吃掉第 i1 棵草之间的时间我们在下面把它叫做第 i1 段时间还没有被吃掉的 n-i 棵草都在流失口感……] [于是我们发现第 i 段时间对答案的贡献为这段时间的长度与 n-i1 的乘积。] [接着我们再来关注最优策略。吃完一棵草后包括初始时奶牛的最优策略一定是直奔另一棵草。] [由于奶牛不会飞所以奶牛走过的所有路一定是一段连续的区间。] [显然地被奶牛经过过的地方按最优策略一定不会留下青草。] [所以我们可以**将所有青草的坐标排序**下面我们都使用排完序后的编号然后用 dp[l][r][j] 表示吃完 [l,r] 范围内的青草时的最小答案j 只有 0,1 两种取值分别表示奶牛吃完最后一棵草停在青草 l 还是 r 上只有可能是这两种情况否则与上面的结论矛盾。] [于是我们就可以轻易地设计出状态转移方程] [dp[l][r][0]min(dp[l1][r][0](n-rl)*abs(x[l]-x[l1]),dp[l1][r][1](n-rl)*abs(x[l]-x[r]))] [dp[l][r][1]min(dp[l][r-1][1](n-rl)*abs(x[r]-x[r-1]),dp[l][r-1][0](n-rl)*abs(x[r]-x[l]))] [边界为dp[i][i][j]abs(x[i]-k)*n对于所有1inj0,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 casefor i in range(1, n 1):dp[i][i][0] dp[i][i][1] abs(x[i] - k) * n# Dynamic programmingfor length in range(2, n 1):for l in range(1, n - length 2):r l length - 1dp[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)
