题目描述

有一座城市，城市中有 $N$ 个公交站，公交站之间通过 $N-1$ 条道路连接，每条道路有相应的长度。保证所有公交站两两之间能够通过唯一的通路互相达到。
两个公交站之间路径长度定义为两个公交站之间路径上所有边的边权和。
现在要对城市进行规划，将其中 $M$ 个公交站定为“重要的”。
现在想从中选出 $K$ 个节点，使得这 $K$ 个公交站两两之间路径长度总和最小。输出路径长度总和即可（节点编号从 $1$ 开始）。

题目描述

给出一棵树，求树的直径及其数量（最长简单路径的长度和数量）。

输入格式

第一行一个整数 $n$ , $0\le n\le10^5$，
接下来有 $n-1$ 行，每行 $a,b$ 代表 $a$ 到第 $b$ 有一条长度为 $1$ 的边。

题目描述

将高为H，宽为W的棋盘分割成若干个宽和高分别为1和2的长方形，有多少种方案。

输入描述

第一行为H$(1≤N≤11)$，W$(1≤W≤11)$。

输出描述

题目描述

给定一个字符串S ，找到其中最长的回文子序列，并返回该序列的长度。

输入描述

输入为一个只包含小写英文字母的字符串S，最大长度不超过4000。

输出描述

题目描述

定义一个合法的括号序列

• 空序列合法
• 如果S合法，那么(S)和[S]合法
阅读全文 »

题目描述

将 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 $N$ 及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 $N - 1$ 次合并得分总和最大。
阅读全文 »

学号202000202092

实验目的

熟悉个人博客系统的搭建。
具体包括：
参考方案：注册Github账号，搭建Hexo环境并实现个人博客搭建，撰写实验报告。

题目描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N$(1≤N≤40)$，V$(1≤V≤10^{15})$。

下面N行，第i行描述第i个物品的w[i]$(1≤w[i]≤10^{15})$，c[i]$(1≤c[i]≤10^{15})$，用一个空格分隔。

题目描述

给定序列 $A =(a_1, a_2,\ldots , a_n)$ 和 $B =(b_1, b_2,\ldots , b_m)$ ，求它们的最长公共子序列

子序列的定义参考题目 最长上升子序列

输入格式

第一行两个整数 $n, m$ 代表序列 $A,B$ 的长度

题目描述

对于一个整数序列 $A =(a_1, a_2,\ldots , a_k)$，定义 $A$ 的子序列为：从 $A$ 中删除若干个元素后（允许不删，也允许将所有 $k$ 个元素都删除），剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增，则称它为 $A$ 的一个上升子序列。其中包含元素数量最多的上升子序列称为 $A$ 的最长上升子序列。例如，$(2, 4, 5, 6)$ 和 $(1, 4, 5, 6)$ 都是 $(2, 1, 1, 4, 7, 5, 6)$ 的最长上升子序列，长度都为 $4$。

那么，给定一个序列 $A =(a_1, a_2,\ldots , a_n)$， 求 $A$ 的最长上升子序列的长度

输入格式

第一行一个整数 $n$ ，代表序列 $A$ 的长度