[Algorithm][综合训练][循环汉诺塔][kotori和素因子][dd爱科学]详细讲解

---

1.循环汉诺塔

1.题目链接

• 循环汉诺塔

---

2.算法原理详解 && 代码实现

• 解法：动态规划

  • 重点：找出重复子问题
    

  #include <iostream>
  using namespace std;const int MOD = 1e9 + 7;int main()
  {int n = 0;cin >> n;int x = 1, y = 2;for(int i = 2; i <= n; i++){int prevX = x, prevY = y;x = (2 * prevY + 1) % MOD;y = ((2 * prevY) % MOD + 2 + prevX) % MOD;}cout << x << " " << y << endl;return 0;
  }
  

---

2.kotori和素因子

1.题目链接

• kotori和素因子

---

2.算法原理详解 && 代码实现

• 解法：DFS枚举所有的情况
  

  #include <iostream>
  #include <cmath>
  #include <vector>
  using namespace std;int n = 0, path = 0, ret = 0x3f3f3f3f;
  vector<int> nums;
  vector<bool> use(1001, false); // 记录哪些值已经被使用过bool isPrim(int x)
  {if(x <= 1){return false;}for(int i = 2; i <= sqrt(x); i++){if(x % i == 0){return false;}}return true;
  }void DFS(int pos)
  {if(pos == n){ret = min(ret, path);return;}// 枚举 nums[pos] 的所有没有使⽤过的素因⼦for(int i = 2; i <= nums[pos]; i++){if(nums[pos] % i == 0 && isPrim(i) && !use[i]){path += i;use[i] = true;DFS(pos + 1);path -= i;use[i] = false;}}
  }int main()
  {cin >> n;nums.resize(n, 0);for(auto& x : nums){cin >> x;}DFS(0);if(ret == 0x3f3f3f3f){cout << -1 << endl;}else{cout << ret << endl;}return 0;
  }
  

---

3.dd爱科学

1.题目链接

• dd爱科学

---

2.算法原理详解 && 代码实现

• 模型抽象：就是最长非递减子序列模型

• 解法：最长递增子序列 --> 贪心 + 二分

  • 贪心：

    • 不关心前面的非递减子序列长什么样子，仅需知道长度为x的子序列末尾是多少即可
    • 存长度为x的所有子序列的末尾时，只用存最小的那个数即可
      

  • 二分优化：因为随着长度，存入字符是递增的，所以在存入长度为x的所有子序列的末尾时，二分查找优化
    

  #include <iostream>
  #include <string>
  using namespace std;const int N = 1e6 + 10;int main()
  {int n = 0;string str;cin >> n >> str;char dp[N];int cur = 0;for(int i = 0; i < n; i++) // 遍历每个位置{char ch = str[i];// 找出ch应该放在记录数组的哪个位置if(cur == 0 || ch >= dp[cur]){dp[++cur] = ch;}else{// 二分找位置int left = 1, right = cur;while(left < right){int mid = (left + right) / 2;if(dp[mid] > ch){right = mid; }else{left = mid + 1;}}dp[left] = ch;}}cout << n - cur << endl;return 0;
  }