使用C语言完成: 游戏规则是这样的:如上图所示所有的小球都布局在一行上,每个小球都有自己的颜色,连续摆放的同颜色小球构成一个小球片段,上图中共有14个小球片段,每个小球片段分别有:5、2、1、2、1、1、1、2、1、1、1、1、1、1个小球片段,玩家每次点击一个小球,则该小球所在的小球片段就会消失。若消失的小球片段中共有m个小球,则玩家获得m*m个积分。请问:给定游戏开始时的状态,玩家可获得的最高积分是多少?输入格式: 第一行是一个整数n(1<=n<=15),表示共有n组测试数据。 接下来每组测试数据共包括两行: (1)第1行是一个整数k(1<=k<=200),表示共有k个小球; (2)第2行包含k个正整数,表示每个小球的颜色这些整数的取值范围是[1,n]。 输出格式: 对每组测试数据,输出玩家可以获得的最高积分,每组数据的输出单独占一行。
时间: 2024-03-18 17:43:52 浏览: 71
这个问题可以使用动态规划来解决。
具体来说,我们可以定义 $f(i,j)$ 表示从第 $i$ 个小球片段开始,到第 $j$ 个小球片段结束,能够获得的最大积分。显然,当 $i=j$ 时,$f(i,j)=m_i^2$,其中 $m_i$ 表示第 $i$ 个小球片段的长度;当 $i<j$ 时,$f(i,j)$ 可以通过以下方式计算:
$$
f(i,j) = \max_{i\leq k<j} \{f(i,k)+f(k+1,j)\}
$$
其中,$k$ 表示消除的小球片段的末尾位置。
具体地,我们可以使用一个二维数组 $f$ 来存储所有的 $f(i,j)$ 值。我们可以先将所有的 $f(i,i)$ 初始化为 $m_i^2$,然后按照从小到大的顺序依次计算 $f(i,j)$,最后返回 $f(1,n)$,即为所求的最大积分。
下面是使用 C 语言实现的代码:
阅读全文