8420: BZOJ4420：[Shoi2013]二重镇

这是一个充满爱的村子，它的名字叫二重镇。在这个爱意浓浓的村子里，居民们的生活快乐又安宁。二重镇呈长条形状，可分为排成一行的N个方格。每个格子可能是空地，也可能是小草、灌木、大树、房屋或城堡中的一种物品。每种物品都有一个等级，小草的等级是1，灌木的等级是2，依此类推。 你是这个村庄的建造者。你会陆续获得D件物品，你要将它们合理地放置在村庄的空地上。你的目标是要让村子的总人气尽可能大。人气的获得规则在后面说明。关于放置的规则有以下几条： 第一，每件物品都必须放在一个地方，不可丢弃，如果没有空地了，游戏直接结束； 第二，物品可以放在一格空地上，或者临时放在仓库里。仓库同时最多只能放一件物品，它一开始是空的。只存在一个仓库； 第三，一旦物品放在某个空格上，只要符合条件，系统就会自动将一些物品合成一个大的物品，这是强制被动的，也是瞬间的。直到合成结束后，才能放置下一个物品。 第四，存放在仓库中的物品，随时可以取出放到空地上（但注意不能在合成的过程中放置），也可以一直留在仓库里。 第五，除非利用仓库，不然不能更改物品的放置顺序； 总结起来，这个游戏的流程就是获得一个新物品，决定是否将这个物品存入仓库，再决定将仓库中的物品或新物品放到哪个空地上，系统自动判定合成，获得人气，直到所有物品都被放置完毕，或空地用完为止。 最后是关于合成的规则。合成是自动完成的，也是强制性的。如果有连续两个或以上相邻的格子里有相同等级的物品，它们会自动合成成一个新的物品，新物品的等级比之前高一个级别。合成分三步： 第一步，确定有多少物品参与合成，这些物品的位置必须连在一起，等级相同。参与合成的物品会全部消失，对应的格子边成空地； 第二步，假设有A个K级物品参与合成，那么将获得A*(2^B)点人气。例如有一次五棵小草进行了合成，那么总人气就会增加5*(2^1)=10； 第三步，一个K+1等级的物品会出现在一个格子里。如果K+1大于5，则跳过这步，但第二步中的人气仍然要算，第一步中的旧物品也会被清除。这个高等级的物品只会出现在参与合成的格子上。每个格子会记录最后一次被放置物品的时间，新的物品会出现在该时间最晚的那个格子里，换而言之，就是出现在最近被放置过东西的格子里； 最后，请注意合成是会触发多次的，比如两个小草合成一个灌木，如果这棵灌木旁边还有其他灌木，合成将继续发生下去。 现在，给出N和获得物品的顺序及等级，请你要合理地将这些物品放置在一个初始全是空地的村子里，使得村子最终的人气值尽可能高。当所有物品都被放置，或者村子不能再放物品了，都会结束村子的建设，而此时村子里累计人气值就是最终成果。

输入格式

第一行给出两个整数N和D，用空格隔开。N表示村庄大小，D表示物品数量。 第二行为一个字符串，每个字符为'1'..'5'之间的一个字符，表示每天你可以放置的物品的等级。

输出格式

输出一个整数，表示你能得到的最大的人气值。

样例输入

4 10
1132411235

样例输出

168
【数据规模】
3<=N<=6
D<=101

提示

没有写明提示

题目来源

没有写明来源