动态规划之方盒游戏

状态是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 
#include 
#define MaxLen 205
using namespace std;
s

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！