LCS——经典的 DP 问题，给定两个长度为 $n$ 的排列，试问二者的最长公共子序列。这是经典的区间 DP 问题， 首先考虑朴素做法，定义 $dp[i][j]$ 来表示第一个串的前 $i$ 位，第二个串的前 $j$ 的 $LCS$ 长度，易得状态转移方程： 如果两个序列没有新的相同元素 $dp[i][j] = \max(dp[i-1][j],dp…

环上最大独立集 题目描述 给出一个有 $n$ 个点的环，每个点有点权 $a_i$，求满足点集内任何两个点在环上不相邻，且点权和最大的点集的点权和。 注意点 $1$ 和 点 $n$ 是相邻的。 输入格式 第一行输入一个正整数 $n$，表示点的数目。 第二行输入 $n$ 个以空格隔开的整数，依次表示各个点的点权 $a_i$。 输出格式 输出一行一个整数…