尘枫--odin 2024-06-14 17:06 采纳率: 0%
浏览 24
已结题

请各位看看我写的属于什么算法,或者有更正确的写法?

有没有人知道这个问题我解答的是否正确?我自己写了一个版本,但是不知道有没有疏漏。
我查了很多资料包括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;
} 

  • 写回答

24条回答 默认 最新

  • 阿里嘎多学长 2024-06-14 17:06
    关注
    获得0.30元问题酬金

    以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳:


    首先,让我们分析你提供的代码和算法逻辑。

    1. 代码逻辑分析

      • 你的代码试图通过去重和合并操作来模拟消消乐游戏的过程。
      • 你使用数组b来存储处理后的砖块数列,并尝试在其中找到最大值。
    2. 代码问题

      • 你的代码中存在一些逻辑错误和潜在的数组越界问题。例如,在while(a[i+1]==chong && i<n)循环中,如果i达到n-1i+1将越界。
      • while(chong==b[k-1])循环中,如果k为1,b[k-1]将访问数组b的第一个元素前的位置,导致未定义行为。
      • 代码中的// 结合部分逻辑不清晰,且可能导致数组b的不正确更新。
    3. 算法是否属于动态规划

      • 动态规划通常用于解决具有重叠子问题和最优子结构特性的问题。你的算法试图通过迭代的方式逐步解决问题,但并没有明显地利用到动态规划的典型特征,如记忆化或状态转移方程。
    4. 优化建议

      • 动态规划解法通常需要定义状态和状态转移方程。对于这个问题,可以考虑使用一个数组来记录每个数字出现的次数,然后依次处理每个数字,如果相邻的数字相同,则消除一个,并更新分数。
      • 一个可能的动态规划状态转移方程是:dp[i] = max(dp[i-1], nums[i] + dp[i-nums[i]] if i >= nums[i]),其中nums是原始数组,dp是动态规划数组,表示到当前位置为止的最大分数。
    5. 正确的动态规划实现方法

      • 一个可能的动态规划实现是使用一个哈希表来记录每个数字出现的次数,然后迭代地消除相邻相同的数字,并更新分数。

    下面是一个简化的动态规划思路,不是完整的代码实现,但可以指导你如何思考这个问题:

    #include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    
    int maxScore(vector<int>& nums) {
        unordered_map<int, int> freq;
        int score = 0;
        for (int num : nums) {
            freq[num]++;
        }
        for (auto it = freq.begin(); it != freq.end(); ++it) {
            if (it->second > 1) {
                int count = it->second;
                int eliminated = count / 2; // 消除的砖块数
                score += eliminated * (it->first + 1); // 更新分数
                freq[it->first + 1] += count % 2; // 更新剩余的砖块数
            }
        }
        return score;
    }
    
    int main() {
        int n;
        cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        cout << maxScore(nums) << endl;
        return 0;
    }
    

    请注意,这个代码只是一个示例,它没有完全实现题目要求的逻辑,但它展示了如何使用动态规划的思想来解决问题。你需要根据题目的具体要求调整和完善这个算法。

    至于参考资料,你可以查找关于动态规划的教程和案例,例如在LeetCode、GeeksforGeeks等网站上搜索相关问题的解决方案。

    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 6月22日
  • 修改了问题 6月14日
  • 创建了问题 6月14日

悬赏问题

  • ¥15 cpuid是如何转换的
  • ¥15 MddBootstrapInitialize2失败
  • ¥15 LCD Flicker
  • ¥15 Spring MVC项目,访问不到相应的控制器方法
  • ¥15 esp32在micropython环境下使用ssl/tls连接mqtt服务器出现以下报错Connected on 192.168.154.223发生意外错误: 5无法连接到 MQTT 代理,如何解决?
  • ¥15 关于#genesiscsheel#的问题,如何解决?
  • ¥15 Android aidl for hal
  • ¥15 STM32CubeIDE下载程序报错
  • ¥15 微信好友如何转变为会员系统?(相关搜索:小程序)
  • ¥15 c# 直接使用c++ 类库文件