7971: BZOJ3971:[WF2013]Матрёшка

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

俄罗斯套娃是一些从外到里大小递减的传统的俄罗斯木头玩偶组成的。当你打开一个俄罗斯套娃时,里面就会露出一个同样的俄罗斯套娃,再打开,就会再露出一个,不断重复。 俄罗斯的俄罗斯套娃博物馆最近收藏了一些外形相似的俄罗斯套娃集,只是里面嵌套的玩偶数量不相等。不幸的是,有一群过分热情的(和明显无人监督的)孩子们拆了他们,并放在一行上。有n个玩偶在一上,每个都有一个整数的大小,你需要重新组装套娃集,你既不知道套娃集的数量,也不知道某个套娃集内玩偶的数量,你只知道一个完好的套娃集内的玩偶大小是从1到某个数字m 在组装套娃集时,你必须遵守下列规则: 1.你只能将一个玩偶或者套娃集放入一个更大的玩偶中 2.你只能把相邻两个俄罗斯套娃组合在一起 3.已经被合并的玩偶是不能再重新拆出来的。 你的时间很宝贵,你只想尽快的组装好。唯一需要耗时的部分为打开一个玩偶并马上关上它。所以你要尽可能少的做这种操作。比如说:合并[1,2,6]与[4],你需要将大小为4和6的两个玩偶拆开。合并[1,2,5]与[3,4]代价为3。 求将n个玩偶重新拼成一些完好的俄罗斯套娃的最小代价。


输入格式

第一行一个数n,第二行包含n个数,依次表示每个玩偶的大小。


输出格式

如果答案存在,输出一个数表示将n个玩偶重新拼成一些完好的俄罗斯套娃的最小代价。否则输出“Impossible”


样例输入

7
1 2 1 2 4 3 3

样例输出

Impossible

提示

1<=n<=500 , 1<=玩偶大小<=500


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: