编程！ 方块消除问题 动态规划

IOI 2003 中国国家集训队讨论题目

黑书 P123 页

求各个变量范围

最好给出源程序 （Pascal）

i,j,k,p 如何定义

求详解 谢谢！
Jimmy最近迷上了一款叫做方块消除的游戏。游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域），如图1-70所示。游戏时，你可以任选一个区域消去。设这个区域包含的方块数为x，则将得到x^2个分值。方块消去之后，其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时，其右边的所有方块就会向左移一格。

图1.
一个完整的游戏过程

上图是一个两个可能的游戏方案，其中第一种是最优的。虽然游戏很简单，但是要拿高分也很不容易。Jimmy希望你能找出得最高分的最佳方案，你能帮助他吗？

【输入格式】

第一行包含一个整数n(1<=n<=200)，表示方块数目。第二行包含n个数，表示每个方块的颜色（1到n之间的整数）。

【输出格式】

仅一个整数，即最高可能得分。

【样例输入】
9
1 2 2 2 2 3 3 3 1

【样例输出】
29

e..貌似少贴了一点点。。
这是O(nm^3)的标程。。m是连续的数字相同的段数，比如样例m=4。。
找不到更好的算法。。好像。。不是很长。。
const
limit =100;
inf ='block.in';
outf ='block.out';

var
n,m :longint;
color,len ,
rest,prev :array[0..limit+1] of longint;
max :array[0..limit+1,0..limit+1,0..limit+1] of longint;

procedure init;
var
i,j :longint;
begin
fillchar(rest,sizeof(rest),0);
fillchar(prev,sizeof(prev),0);
fillchar(max,sizeof(max),0);
assign(input,inf);reset(input);
read(n);
read(color[1]);
len[1]:=1;
m:=1;
for i:=2 to n do
begin
read(j);
if j=color[m] then inc(len[m])
else begin
inc(m);
color[m]:=j;
len[m]:=1;
end;