有没有人知道这个问题我解答的是否正确?我自己写了一个版本,但是不知道有没有疏漏。
我查了很多资料包括AI都告诉我应该用动态规划,但是我不知道自己的写法到底算不算,所以我一方面想知道自己用的属于什么算法,另一方面希望能有人解答一下这个问题如何利用动态规划解决,万分感谢!!
C++编程实现:
小蓝在玩一款消消乐游戏,游戏规则如下:
1.游戏初始时有若干个砖块排成一行,每个砖块上有一个数:
2.找出这一行砖块中两个相邻且数相同的砖块,消除其中一个砖块,剩下砖块上的数
加1(例如:两个相邻砖块上的数都为6,消除后剩下一个砖块,此砖块上的数改为7);
3.不停的重复第2步,直到这一行没有可以消除的砖块时,游戏结束,此时,游戏分数
就是这行砖块里面最大的数。
注意:不同的砖块消除次序得到的游戏分数可能不同。
现在给定了一个正整数数列,表示游戏初始时每个砖块上的数,请你计算这次游戏的最
高分数。
例如:
游戏初始有六个砖块排成一行,砖块上的数依次为1 2 2 2 3 4,得到游戏最高
分的方法如下:
先将后面两个数为2的砖块消除其中一个,另一个砖块上的数变为3,此时剩余5个砖块
上的数依次为1 2 3 3 4:
然后将两个数为3的砖块消除其中一个,另一个砖块上的数变为4,此时剩余4个砖块上
的数依次为1 2 4 4:
最后将两个数为4的砖块消除其中一个,另一个砖块上的数变为5,此时剩余3个砖块上
的数依次为1 2 5;
此时没有可以消除的砖块,这行砖块里面最大的数是5,故输出5。
输入描述:
第一行输入一个正整数N(1≤N≤500000),表示游戏初始砖块的数量:
第二行输入N个正整数(1≤正整数≤80),依次表示每个砖块上的数,相邻两个数之间
用一个空格隔开。
输出描述:
一个正整数,表示这次游戏的最高分数。
样例输入:
6
122234
样例输出:
5
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int a[n],b[n+1] = {},k = 1,max = -1;
for(int i = 0; i < n; i++)cin >> a[i];
for(int i = 0; i < n; i++){
int chong = a[i],num = 1;
// 去重
while(a[i+1]==chong && i<n-1)num++,i++;
while(chong==b[k-1])k--,num++;
b[k] = chong;
while(num>1){
num/=2;
b[k]++;
}
// 结合
while(b[k]==b[k-1] && b[k]!=a[i+1]){
b[k-1]++;
b[k] = 0;
k--;
}
if(b[k]>max)max = b[k];
k++;
}
// 数组检查
for(int i = 1; i <= n; i++)cout << b[i] << ' ';
cout << endl;
// 最大值输出
cout << max;
}