2020-team12-C05

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

== Ranklist ==

[[Image(2020-C05.png,800px)]]

== Submisson ==

[[Image(2020-C05submission1.png)]]
[[Image(2020-C05submission2.png)]]
[[Image(2020-C05submission3.png)]]



== 概述 ==

solved: 6/13  dirt: 33.3%

rank: 5

题解和反思：
A.水签到，由于选错了文件夹错交了一发。

B.水签到。

C.按层{{{#!latex $O(n^2)$dp}}}即可。

D.

E.题意：给n=500的字符串和一个连消数m，其由多种颜色的球组成，消除规则类似祖玛。问串是否可以消除。
题解：考虑区间dp判断,dp[i][j]表示i到j能否消除。首先两个可消除的串并在一起是可消除的；其次第二种就是中间有一些相同的字符(ABBBACCCADDDAEEEA)，并且他们之间可以合并。
需要抽出中间的位置来进行DP转移，g[k]表示（某一个字符串里）直到第k个串最多可以连几个，（针对某一个区间来说的第i个位置）
whn-7发，错误很多。第一发根本没管“两头字母要相同”，第二-三发只管了中间一段的情况，第四发以为只需要贪心选择不需要DP，直到最后都没注意初始值。 
反思： 以后一定要分析清楚哪些状态是必须kill的，初值必须设置成-INF.

F.

G.

H.

I.

J.

K.

L.

M.

[/wiki/2020-team12 返回]