POJ 1738 An old Stone Game（石子合并）-白红宇

POJ 1738 An old Stone Game（石子合并）

阅读量：793 次

发布时间：2023-03-03

本文共 1282 字，大约阅读时间需要 4 分钟。

题目要求我们将n堆石子合并成一堆，且每次合并相邻两堆石子代价为这两堆石子的重量之和，目标是找到最小的代价。常规的动态规划方法在n较大的情况下会超时，因此我们需要寻找一种更优化的解法。

贪心算法的思路：

寻找特定条件下的最小堆：首先，我们需要找到一个最小的i，使得A[i-1] <= A[i+1]。这一步确保了合并后不会导致更大的代价增加。

合并最小的堆：找到满足条件的i后，将A[i-1]和A[i]合并为一个临时堆temp。

重新排列堆的顺序：找到前面最大的j，使得A[j] > temp，将temp放在j之后。这样可以确保后续的合并过程中不会产生更大的代价。

重复上述步骤：直到只剩下一堆石子为止。

代码实现：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              using namespace std; void combine(int k, vector
             
              & a) { int temp = a[k-1] + a[k]; a[k] = temp; a.erase(a.begin() + k-1); return; } void RD(int& x) { scanf("%d", &x); } int main() { int n; vector
              
                a; while (scanf("%d", &n) != -1) { if (n == 0) break; a.clear(); for (int i = 0; i < n; ++i) { int num; RD(num); a.push_back(num); } if (n == 1) { cout << 0 << endl; continue; } vector
               
                 temp; for (int i = 0; i < a.size(); ++i) { temp.push_back(a[i]); } while (temp.size() > 1) { int min_pos = 0; for (int i = 1; i < temp.size(); ++i) { if (temp[i-1] <= temp[i+1]) { min_pos = i; } } combine(min_pos, temp); } cout << temp[0] << endl; } return 0; }

代码解释：

输入处理：读取输入的n和石子堆的重量。

前缀和处理：计算前缀和以便快速计算任意区间的和。

堆的合并模拟：使用一个双端队列或栈来维护石子堆的顺序，按贪心算法步骤进行合并。

输出结果：输出最小代价。

这种方法通过每次合并选择最优的堆，确保最终代价最小，时间复杂度为O(n log n)，适用于较大的n值。

转载地址：http://auxfk.baihongyu.com/

你可能感兴趣的文章

pip throws TypeError: parse() got an unexpected keyword argument ‘transport_encoding‘ 在尝试安装新软件包时