动态规划之方盒游戏

状态是ClickBox( i , j , extralen)表示在大块 j 的右边已经有一个长度为 extralen 的大块，且其颜色与大块 j 相同，将大块 j 和大块 extralen 合并称为大块Q，在此情况下，将大块 i~j 以及大块 extralen 都能消除所得到的最高分。

整个问题就是求ClickBox( 1 , n , 0 )

状态转移方程：

1. 直接将Q删除，这种做法得到的最高分是

ClickBox( i , j , extralen ) = ClickBox( i , j-1 , 0 ) + (len[ j ] + extralen)^2;

2. 期待Q以后能和左边的某个同色大块合并。需要枚举可能和大块Q合并的同色大块。假设让大块k和大块Q合并

ClickBox( i , j , extralen ) = ClickBox( i , k , extralen + len[ j ] ) + ClickBox( k+1, j-1 , 0 )

递归终点是当 i = j 时，  ClickBox( i , j , extralen ) = (len[ j ] + extralen) ^ 2

#include <iostream>
#include <memory.h>
#define MaxLen 205
using namespace std;
s