动态规划7--方盒游戏

一、心得

直接根据问题写状态
如果不能写出状态转移方程，就多维（细化），直至能够写出状态转移方程。

二、题目和分析

题意：
N个方盒(box)摆成一排，每个方盒有自己的颜色。连续摆放的同颜色方盒构成
一个方盒片段(box segment)。下图中共有四个方盒片段，每个方盒片段分别有
1、4、3、1个方盒
玩家每次点击一个方盒，则该方盒所在方盒片段就会消失。若消失的方盒片段

中共有k个方盒，则玩家获得k*k个积分。

思路：区间dp
首先将每个连续颜色的盒子看成一个“块”
click_box(i,j,exlen)代表从i到j以及exlen消除掉可以得到的最高分
exlen表示j右边的“块”，这个块可能不是最初的块，可能是消掉一部分块后形成的
且j的颜色和exlen相同
目标状态： click_box(0,n-1,0)
递推过程
1.直接将j和exlen消除掉
得到click_box(i,j-1,0) + (len[j]+exlen)^2
2.不消除j和exlen，以待以后消除得到更高的分数，贪心啊哈，
更新exlen为len[j]+exlen，假设又和k块颜色相同了（k在i和j之间）

可以得到click_box(i,k,len[j]+exlen) + click_box(k+1,j-1,0)

三、代码

核心代码

 1 /*
 2 动态规划7--方盒游戏
 3 进一步细化之后（复杂化，多维化）
 4 click_box(i,j,ex_len)
 5 表示：
 6 大块j的右边已经有一个长度为ex_len的大块，且j的颜色和ex_len相同，
 7 在此情况下将i到j以及ex_len都消除所能得到的最高分
 8 初始状态： click_box(0,n-1,0)
 9 
10 递推关系：
11 求click_box(i,j,ex_len)时，有两种处理方法，取最优者，
12 假设j与ex_len合并后的大块称作Q
13 1）将Q直接消除，这种做法能得到的最高分就是:
14 click_box(i,j-1,0)+(len[j]+ex_len)^2
15 2) 期待Q以后能和左边的某个同色大块合并。需要枚举可能和W合并的大块。
16 假设让大块k和W合并，则此时能得到的最大分数是：
17 click_box(i,k,len[j]+ex_len)+click_box(k+1,j-1,0) 
18 
19 递归终止条件：
20 i==j
21  
22 */
23 #include <cstring>
24 #include <iostream>
25 using namespace std;
26 struct Block{
27     int color;
28     int len;
29 }; 
30 struct Block segment[200];
31 int score[200][200][200];//记忆化递归，存放计算结果，避免重复计算
32 int click_box(int start,int end,int extra_len){
33     //第一种情况  1）将Q直接消除，这种做法能得到的最高分就是:
34     int i,result,temp;
35     //如果score[start][end][extra_len]被计算过，就直接返回 
36     if(score[start][end][extra_len]>0)
37         return score[start][end][extra_len];
38     result = segment[end].len+extra_len;//这个就是Q
39     //将Q直接消除 
40     result = result*result;//end和extra_len一起消去的得分
41     //头和尾相同了，没得消除的了 
42     if(start==end){//递归终止条件 
43         score[start][end][extra_len]=result;
44         return score[start][end][extra_len]; 
45     } 
46     result += click_box(start,end-1,0);
47     
48     //第一种情况 
49     
50     //------------------------------------------------------------------ 
51     
52     //第二种情况  2) 期待Q以后能和左边的某个同色大块合并。
53     i=end-1;
54     for(i=end-1;i>=start;i--){//从最后往前找和Q颜色相同的方盒 
55         //如果方盒颜色不同，不能合并 
56         if(segment[i].color!=segment[end].color)
57             continue;
58         //下面执行颜色相同的情况
59         //也就是第二种情况 
60         temp=click_box(start,i,segment[end].len+extra_len)+click_box(i+1,end-1,0);
61         if(temp<=result) continue;
62         //如果temp大，那么result变成temp 
63         result=temp; 
64     }
65     
66     //将第一种情况和第二种情况中的较大值返回 
67     score[start][end][extra_len]=result;
68     return score[start][end][extra_len]; 
69 }