【一只蒟蒻的刷题历程】--- 问题 1427: [蓝桥杯][2013年第四届真题]买不到的数目（动态规划）-白红宇

【一只蒟蒻的刷题历程】--- 问题 1427: [蓝桥杯][2013年第四届真题]买不到的数目（动态规划）

阅读量：279 次

发布时间：2019-03-01

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

为了解决这个问题，我们需要找到在给定的两种包装糖果颗数n和m的情况下，最大不能通过组合这两种包装得到的糖果数。我们可以使用动态规划的方法来解决这个问题。

方法思路

问题分析：我们需要找到最大的数，这个数无法表示为ax + by，其中a和b是非负整数，x和y分别是n和m的数量。

动态规划：创建一个布尔数组dp，dp[i]表示i颗糖果是否可以被组成。初始化dp[n]和dp[m]为True，因为直接购买n或m颗糖果是可以的。

遍历检查：从1到n*m的每一个数i，检查i是否可以通过减去n或m得到的数是否已经被标记为可行。如果是，则标记i为可行。

找到最大无法组合的数：从n*m开始倒序检查，找到最大的无法被组成的数。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int main() { int n, m; cin >> n >> m; int max_num = n * m; bool dp[max_num + 1]; // 初始化所有为false fill(dp, dp + max_num + 1, false); dp[n] = true; dp[m] = true; for (int i = 1; i <= max_num; ++i) { if (i == n || i == m) { dp[i] = true; } else { int a = i - n; int b = i - m; if (a >= 0 && dp[a]) { dp[i] = true; } else if (b >= 0 && dp[b]) { dp[i] = true; } } } // 从max_num开始倒序查找第一个无法组成的数 for (int i = max_num; i >= 0; --i) { if (!dp[i]) { cout << i << endl; return; } } return;}

代码解释

输入读取：读取n和m的值。

数组初始化：创建一个布尔数组dp，长度为n*m + 1，初始值为false。然后标记n和m为true，因为它们可以直接购买。

动态规划填充：遍历从1到n*m的每一个数i，检查i是否可以通过减去n或m得到的数是否已经被标记为可行。如果是，则标记i为true。

寻找最大无法组合的数：从n*m开始倒序检查，找到第一个无法被组成的数并输出。

这种方法确保了我们能够正确地计算出最大无法组合的数，时间复杂度为O(n*m)，在n和m都不超过1000的情况下是可行的。

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

你可能感兴趣的文章