四、动态规划（2）--方盒游戏

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

struct block
{
    int color;
    int len;

};

block  segment[200];
int score[200][200][200]; //存放计算结果， 避免重复计算

int click_box(int start, int end, int ex_len){
    int i, result;
    if (score[start][end][ex_len] > 0)
        return score[start][end][ex_len];
    //最后一块喝ex_Len是同一样颜色的块，直接合并
    result = segment[end].len + ex_len;
    result = result * result; 
    //如果是最后一块，返回结果
    if (start == end){
            score[start][end][ex_len] = result;
            return score[start][end][ex_len];
    }

    //递归计算
    score[start][end][ex_len] = result+ click_box(start, end - 1, 0);
    //不直接消除最后的盒子
    for (i = start; i<end; i++){
        if (segment[i].color == segment[end].color)
            score[start][end][ex_len] = max(score[start][end][ex_len], click_box(start, i, segment[end].len + ex_len) + click_box(i + 1, end - 1, 0));
    }
    return score[start][end][ex_len];
}


int main(){
    int t, n, i, j, end, color;
    cout << "-------------------------" << endl;
    cout << "输入测试组（1- -15）：";
    cin >> t;
    for (i = 0; i < t; i++){
        cout << "输入盒子数量:n(1--200)：";
        cin >> n;
        end = 0;
        cout << "输入盒子颜色：";
        cin >> segment[end].color;
        segment[end].len = 1;
        for (j = 1; j < n; j++){
            cin >> color;
            if (color == segment[end].color) segment[end].len++;
            else
            {
                end++;
                segment[end].color = color;
                segment[end].len = 1;
            }
        }
        memset(score, 0, sizeof(score));
        cout << "-------------------------" << endl;
        cout << "case  " << i + 1 << " 的积分最高为: " << click_box(0, end, 0) << endl;
    }
    return 0;

}

【参考文档】

1.poj1390解题报告