欢迎大家~里面讲的还算细致！
@AC君 求加精
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1 染色（非官方解法）-- 洛谷试验通过
P17014 [GESP202606 七级] 染色
题目：
小杨同学有一张包含 nnn 个结点的无向图 GGG，GGG 中的结点依次以 1,2,…,n1,2,\dots,n1,2,…,n 编号。
小杨同学发现 GGG 中每个结点的度数都是 222。显然 GGG 中恰好有 nnn 条边。
小杨同学想为 GGG 中的结点染色，使得任意一条边两端的结点都有不同的颜色。
小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为 GGG 染色。
本题包含多组数据。
第一行，一个正整数 ttt，表示数据组数。
对于每组数据：
第一行，一个正整数 nnn，表示无向图 GGG 中的结点数。
接下来 nnn 行，每行两个正整数 ui,viu_i,v_iui ,vi ，表示一条连接结点 uiu_iui 与 viv_ivi 的无向边，整数之间以空格分隔。
保证 GGG 中没有重边与自环。
对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 GGG 染色需要的最少颜色数。
对于 40%40\%40% 的测试点，保证 ∑n≤500\sum n \le 500∑n≤500，∑n\sum n∑n 指每个输入中多组数据的 nnn 的总和。
对于所有测试点，保证 1≤t≤1001 \le t \le 1001≤t≤100，3≤n≤1053 \le n \le 10^53≤n≤105，∑n≤105\sum n \le 10^5∑n≤105。保证 GGG 中没有重边与自环。
题目大意：
给定一个 nnn 个结点的无向图 GGG
图 GGG 中恰好有 nnn 条边
先要为 GGG 图进行染色，使得图中任意被同一条边连接的 222 个结点都能被染上不同的颜色
求：最少需要多少种颜色才能将图 GGG 染成符合染色要求的图？
解题思路：（大拆小，小组大）
PART1 无向图组成分析
题目中说每个点度数都为 222，所以这个无向图一定是由一个个“环”组成的
可能有人不知道为什么是这样：因为题目中说了保证 GGG 中无重边和自环，也就是说，一个节点的度数 222 一定连接另外 222 个结点。那如果每个结点都连接另外 222 个结点，则一定成为若干个环
实在不行画个图：
就像这样，不难发现，无论有多少个结点，都会成为若干个环
> 无向图中结点 uuu 的度数指：与结点 uuu 直接相连的边的总条数
PART2 环上色方案分析
那既然我们已经探究出了“环”，那就在“环”上深入研究吧
我们思考两种可能
* 第一种：有一个 444 个结点的环：1→2→3→4→11 \rightarrow 2 \rightarrow 3 \rightarrow 4\rightarrow 11→2→3→4→1
这种情况下，我们只需要 222 种颜色即可
下面是可能的一种方案：
* 第二种：有一个 555 个结点的环：1→2→3→4→5→11 \rightarrow 2 \rightarrow 3 \rightarrow 4\rightarrow 5 \rightarrow 11→2→3→4→5→1
这种情况下，我们需要 333 种颜色
下面是可能的一种方案：
之所以不能用 222 种颜色涂完，是因为无论怎样，总会有一个点（奇数=偶数+1奇数 = 偶数 +1奇数=偶数+1）被孤立
所以我们可以猜测一个基本规律： 对任意无向简单图，若图内存在任意一条顶点数量为奇数的环，那么不存在仅 222 类颜色、使相邻顶点颜色互不相同的着色方案，完成合法着色至少需要 333 种颜色；若图中所有环的顶点数量均为偶数，则仅两种颜色即可实现合法着色。
PART3 判断方案分析
从环结点数量入手不好分析，所以我们换种思路
我们可以先假设当前这个环是可以用两种颜色染完的
然后我们发现最关键的特征“两种颜色”，天然形成二分图结构
那这道题就演化成了：在一张无向图上进行二分图染色
对于每个环的染色过程中：
* 如果当前节点已经被染色，跳过该节点
* 如果当前节点未被染色，则将其染成其两侧某一节点的相反颜色
* 染色结束之后，如果发现某一节点与其两侧任意一节点颜色相同，则整体需要 333 种颜色，否则 222 种颜色即可
PART4 代码关键部分实现方案分析
分 222 个部分
第一部分：二分图染色
这部分就很简单了，基本属于板子题稍微改一点点
定义 color 数组，记录每个顶点的颜色
对于第 iii 个顶点：
colori=−1color_i = -1colori =−1 代表第 iii 个结点未上色
colori=0color_i = 0colori =0 代表第 iii 个结点上色成颜色1
colori=1color_i = 1colori =1 代表第 iii 个结点上色成与颜色1相反的颜色
最终：对于所有结点 iii，一旦有某个顶点 jjj（ jjj与 iii 相连）的 colorj=coloricolor_j = color_icolorj =colori ，则直接返回 false，若所有结点遍历完毕后都通过，则返回true
这部分的核心代码：
第二部分：初始化+遍历所有连通环
这部分就不用说了吧……最基础的知识
洛谷亲测AC代码
复杂度
时间复杂度：O(t(n+m))O(t (n + m))O(t(n+m))
空间复杂度：O(n+m)O(n+m)O(n+m)
T2 消消乐（尝试往官方解法上靠）-- 洛谷亲测通过
P17015 [GESP202606 七级] 消消乐
题目：
给定一个由nnn个整数构成的数组a=[a1,…,an]a=[a_1,\dots,a_n]a=[a1 ,…,an ]。每次你可以对数组aaa进行以下操作，直到数组aaa变为空：
* 指定aaa中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从aaa中删去。
特别地，如果相邻元素不存在则该元素的该侧值视为000。例如，对于a=[1,2,3]a=[1,2,3]a=[1,2,3]可以进行以下操作：
* 指定元素222，获得分数1+31+31+3，删去222后a=[1,3]a=[1,3]a=[1,3]；
* 指定元素111，获得分数0+30+30+3，删去111后a=[3]a=[3]a=[3]；
* 指定元素333，获得分数0+00+00+0，删去333后aaa变为空。
请问你能获得的分数总和最大是多少？
第一行，一个正整数nnn，表示数组长度。
第二行，nnn个非负整数a1,…,ana_1,\dots,a_na1 ,…,an ，表示数组aaa中的整数。
输出一行，一个整数，表示能获得的最大分数总和。
对于40%40\%40%的测试点，保证1≤n≤501 \le n \le 501≤n≤50，0≤ai≤1030 \le a_i \le 10^30≤ai ≤103。
对于所有测试点，保证1≤n≤1001 \le n \le 1001≤n≤100，0≤ai≤1090 \le a_i \le 10^90≤ai ≤109。
题目大意：
给定长度为 nnn 的数组 aaa，重复进行删除操作直到数组中无数字为止。
每次删除 aia_iai 时，可获得的分数为 ai−1+ai+1a_{i-1} + a_{i+1}ai−1 +ai+1 ，两数中任意一数不存在则加分为 000
求删除完毕元素后能获得的最大分数总和
解题思路：(以终为始、数学推导）
PART1 核心特征分析
如果一段闭区间 [l,r][l,r][l,r] 中最后一个删除的元素的下标是 kkk
则代表：
* 在删除代表 aka_kak 的那一项之前，所有在区间 [l,k−1][l, k-1][l,k−1] 和 [k+1,r][k + 1, r][k+1,r] 的元素应该全部删干净了
* 在删除 aka_kak 的那一刻，左边的元素为 a[l−1]a[l-1]a[l−1]，右边的元素为 a[r+1]a[r+1]a[r+1]，所以删除 aka_kak 时，得分一定是 a[l−1]+a[r+1]a[l-1] + a[r + 1]a[l−1]+a[r+1]
* 因此 总分数=删ak左边[l,k−1]元素的最高分+删ak右边[r,k+1]元素的最高分+删ak得到的固定得分总分数=删a_k左边[l,k-1]元素的最高分+删a_k右边[r,k+1]元素的最高分+删a_k得到的固定得分总分数=删ak 左边[l,k−1]元素的最高分+删ak 右边[r,k+1]元素的最高分+删ak 得到的固定得分
PART2 模型匹配分析
既然有“区间”和“最高分”的概念，直接匹配区间dp
PART3 区间DP定义分析
这个不用说了，直接定义dp数组，其中 dplr{dp_l}_rdpl r 代表将数组下标范围 [l,r][l,r][l,r] 内元素全部删除能获得的最大分数
PART4 初始化与边界条件分析
当 l=rl=rl=r，也就是说只有一个数字的时候，删那一项对于区间来说左右无元素，因此 dp[l][r]=0dp[l][r]=0dp[l][r]=0
其他元素默认初始值都为 000 （你要是想赋值成极小值我也不反对）
PART5 状态转移方程分析
由于上面已经说过了总分数的计算规则（part1讲的），所以很容易看出
PART6 答案分析
也是区间dp的老伙伴，直接输出 dp[1][n]dp[1][n]dp[1][n]
PART7 易错点
十年OI一场空，不开long long见祖宗！\huge{\text{十年OI一场空，不开long long见祖宗！}}十年OI一场空，不开long long见祖宗！
洛谷亲测AC代码
复杂度
时间复杂度：O(n3)O(n^3)O(n3)
空间复杂度：O(n2)O(n^2)O(n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有啥不对的，直接喷！
欢迎各位大佬指点！
点 点 赞 呗\huge{\text{\orange 点 \pink 点 \blue赞 \purple 呗}}点 点 赞 呗
祝点赞的：吉星高照、鸿运当头、时来运转、福运绵长、天随人愿、诸事顺遂、否极泰来、福星临门、好运连连、百事大吉、得天独厚、逢凶化吉、天赐良机、福至心灵、顺风顺水、祥瑞常伴、喜从天降、瑞气盈门、万事亨通、洪福齐天、吉人天相、一路坦途、承天之佑、佳运相伴、多福多喜、青云直上、金榜题名、独占鳌头、学业精进、才高八斗、蟾宫折桂、学有所成、笔底生花、博文广识、登科及第、勤学致远、才思泉涌、学业大成、拔萃出群、满腹经纶
鹏程万里、前程似锦、独占魁首、研精覃思、厚积薄发、一举夺魁、笃学有成、学海扬帆、才学兼备、妙笔生花
财源广进、金玉满堂、富贵盈门、日进斗金、财运亨通、堆金积玉、腰缠万贯、财星高照、招财进宝、富贵荣华
黄金万两、生财有道、财禄双全、广纳财源、富贵常临、金银满库、钱途无量、利达三江、丰财聚宝、财气冲天
福禄双全、福财双至、运旺财兴、登科纳财、才富兼备、顺运生财、及第兴家、福盈财满、鸿财大展、祥财永驻
求学顺遂、财源滚滚、福运双收、才旺财丰、逢考必过、千金在握、天赐富贵、勤学聚财、万事生金、及第纳福
