#P1640. 祖玛(zuma) 代码
时间: 2024-05-04 11:20:42 浏览: 22
以下是祖玛游戏的代码,使用C++实现:
```c++
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n, ans; // n表示小球的个数,ans表示最少需要几次操作
char s[200];
int find(int l, int r) // 找到最长的一段相同颜色的小球
{
int i = l, j = r;
while (i < j)
{
while (i < j && s[i] == s[i+1]) i++;
while (i < j && s[j] == s[j-1]) j--;
if (i < j && s[i] == s[j]) i++, j--;
else break;
}
return i;
}
void solve()
{
ans = n;
for (int i = 0; i < n; i++)
{
int j = find(i, n-1);
if (j < n-1) // 如果有可以消除的小球
{
int k;
for (k = j+1; k < n; k++)
if (s[k] != s[j]) break; // 找到第一个与s[j]颜色不同的小球
for (int l = k-j; l >= 0; l--)
{
// 枚举将s[j]和后面的l个小球消除
int start = max(0, i-l); // left
int end = min(n-1, j+1); // right
for (int r = start; r <= end; r++)
{
int t = find(start, end);
char c = s[t];
int len = t - r + 1;
for (int p = t+1; p < n; p++) s[p-len] = s[p]; // 将后面的小球向前移len个位置
n -= len;
ans = min(ans, l+1 + solve()); // 递归
n += len;
for (int p = n-1; p >= t+1-len; p--) s[p+len] = s[p]; // 将小球复原
for (int p = t-l+1; p <= t; p++) s[p] = c;
}
}
break;
}
}
}
int main()
{
while (cin >> s && s[0] != 'E')
{
n = strlen(s);
solve();
cout << ans << endl;
}
return 0;
}
```
该代码使用了分治法,对于每个区间,找到其中最长的一段相同颜色的小球,然后枚举将这一段小球和之后的小球一起消除的情况,递归求解。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)