1+2=3 题解

· · 题解

官方题解

第一个部分分是爆搜，第二个是记忆化。

A 性质是随便写的贪心就能过。C 性质是给的推出来贪心策略而不是直接求答案的人。

众所周知我是良心出题人，所以这题必然不可能让你巨大分类讨论，你首先要坚信这题有简单做法。

直接考虑构造策略是困难的，可以换个角度，考虑答案的上界，有一个比较明显的是 \min(1-?,?-2)+\min(2-?,?-1)。如果上界能取到的话，也就是说每个 \min 里面较小的值对应的每一个木棒都能和对应的拼上。可以发现 B 性质满足条件。想到这里的话造小数据对拍不断修正应该就可以得到正解了。

考虑为什么有时会不够每一个都能和对应的拼上。如果所有的都是 1-2，你需要拼成一条链，就有一个拼不上。2-1 同理。

但这样还不够。按照上面方式计算出的是所有木棒围成一个环的答案，而要求的是一条链，所以计算出的答案等于所有非 0-0 木棒数量的和，那么答案要减一。

如果对这个做法的可行性有疑问，可以这样理解，这也是构造方案：对于一个 i-1 和 2-j，把这两个“粘贴”在一起，答案+1，同时把这两个删除，变成一个 i-j。2+1 同理。这样就能构造出上面求的答案，而最优性上面已经说了。

赛时发现了很多其他做法，欢迎来写题解！