Browsed by
Tag: dp

atcoder abc142 E题Get Everything 题解

atcoder abc142 E题Get Everything 题解

终于把ABCD全做出来,可以挑战到E题了 题意: 有N个宝箱,标记序号为1到N。商店中有M把钥匙在销售。第i把钥匙售价ai,它能开的宝箱子有bi个,分别是ci,1,ci,2,…ci,bi,现希望将所有N个箱子都打开,试求买钥匙的最小花费。若不可能打开所有宝箱,则输出-1。数据范围:N不超过12,M不…

Read More Read More

数字三角 [SCU – 1114]

数字三角 [SCU – 1114]

简单的动态规划,但是此题需要把路径记下来, 动态规划得从几近成功开始考虑,比如只有2的情形,只需要选两侧更大的那个即可。3层的时候就假设第2层已经知道最大收益,那就选走了第2层以及加上走第2层的收益最大的那个。每次走把当前选的是左还是右记下来,当走到最上层的时候,再反着去读走的那条路径即可。 应该还…

Read More Read More

动态规划两题浅析

动态规划两题浅析

Q1 [AtCoder-4522] 有一蛙,立于1号岩石上,目标是要跳到N号石头上,每次它可以跳到前边一块或隔一块。两石头的高度差的绝对值是青蛙每次跳跃的代价,试问青蛙到终点时可以消耗的最小代价值为多少 解析 动规一般从小规模开始算,假设蛙在第N-1的石头上,只有1种跳法,即代价为cost[N-1]…

Read More Read More

复读子串 Repeated Subsequences [EOlymp – 3624]题解

复读子串 Repeated Subsequences [EOlymp – 3624]题解

最长公共子列问题。 这个题的时限特别长,是10秒钟,看来似乎是可以枚举串的所有分组并逐一计算LCS。 先写能够计算最长公共子序列的函数,然后对每种切分方式(遍历所有可切分的点),分别计算两串的最长公共子序列,记下最长的长度和序列,然后输出最长的那个序列即可。此题思路不难,关键在于如何输出最长公共子序…

Read More Read More