YTU3653: 方盒游戏 动态规划 c++

目录

题目描述

输入

输出

这是代码，自己都大受震撼

希望再也不要让我遇到这道题！！

题目描述

NNN 个方盒摆成一排，每个方盒有自己的颜色，如图所示。连续摆放的同颜色方盒构成一个“大块”

玩家每次点击一个方盒，则该方盒所在大块就会消失。若消失的大块中共有 kkk 个方盒，, 则玩家获得 k×kk \times kk×k 个积分。

请问：给定游戏开始时的状态，玩家可获得的最高积分是多少?

输入

第一行是一个整数 ttt (1≤t≤15)(1 \le t \le 15)(1≤t≤15)，表示共有多少组测试数据。每组测试数据又包括两行:
首先是一个整数 nnn (1≤n≤200)(1 \le n \le 200)(1≤n≤200)，表示共有多少个方盒; 其次包括 nnn 个整数，表示每个方盒的 颜色。这些整数的取值范围是 [1,n]\left[1, n \right][1,n]。

输出

对每组测试数据，分别输出该组测试数据的序号，以及玩家可以获得的最高积分。

这是代码，自己都大受震撼

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;struct sbtz
{int color;int len;
};
struct sbtz box[205];
int ans[205][205][205];int sb_box(int start, int end, int lens)
{int t1, t2;if (ans[start][end][lens] > 0)return ans[start][end][lens];t1 = box[end].len + lens;t1 = t1 * t1;if (start == end){ans[start][end][lens] = t1;return ans[start][end][lens];}t1 = t1 + sb_box(start, end - 1, 0);for (int i = end - 1; i >= start; i--){if (box[i].color == box[end].color){t2 = sb_box(start, i, box[end].len + lens) + sb_box(i + 1, end - 1, 0);if (t2 > t1) {t1 = t2;}}}ans[start][end][lens] = t1;return ans[start][end][lens];
}int main()
{int t, n;cin >> t;for (int i = 1; i <= t; i++){cin >> n;int num = 0;cin >> box[num].color;box[num].len = 1;for (int j = 1; j < n; j++){int cc;cin >> cc;if (cc == box[num].color)box[num].len++;else{num++;box[num].len = 1;box[num].color = cc;}}memset(ans, 0, sizeof(ans));cout << "Case " << i << ": " << sb_box(0, num, 0) << endl;}return 0;
}

希望再也不要让我遇到这道题！！

实在是自己做不出来，太菜了，具体参考了这位大佬的文章：动态规划——方盒游戏详解_算法解占位盒游戏_*远方的博客-CSDN博客d