[Algorithm][综合训练][四个选项][接雨水]详细讲解

---

1.四个选项

1.题目链接

• 四个选项

---

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

• 解法：DFS(暴搜) + 剪枝 + Hash

  • 剪枝：
    • 填某个数的时候，要看看还有没有剩余次数
    • 填某个数的时候，符不符合若干题的选项必须相同
      

  #include <iostream>
  #include <vector>
  using namespace std;int m, x, y;
  int cnt[5];
  bool same[13][13]; // 存哪些答案是相同的int ret = 0;
  vector<int> path;// pos位置填入cur选项是否合法
  bool IsSame(int pos, int cur)
  {// 这里位置限制的比较妙for(int i = 1; i < pos; i++){if(same[pos][i] && path[i] != cur){return false;}}return true;
  }void DFS(int pos)
  {if(pos > 12){ret++;return;}for(int i = 1; i <= 4; i++) // 枚举四个选项{if(cnt[i] == 0) // 没有使用次数{continue;}if(!IsSame(pos, i)) // 相同的位置没有相同{continue;}cnt[i]--;path.push_back(i);DFS(pos + 1);cnt[i]++;path.pop_back();}
  }int main()
  {for(int i = 1; i <= 4; i++){cin >> cnt[i];}cin >> m;while(m--){cin >> x >> y;same[x][y] = same[y][x] = true;}path.push_back(0); // 占位DFS(1);cout << ret << endl;return 0;
  }
  

---

2.接雨水

1.题目链接

• 接雨水

---

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

• 解法：

  • 思路解析：

    • 求出每一根柱子上能接多少雨水，把所有柱子累加起来即可
    • 每根柱子上能接多少雨水，取决于两侧最高的柱子中较小的那个
      

  • 动态规划 -> 预处理：前缀最大值 -> 要算上该位置本身去求前缀最大值
    

  int trap(vector<int>& height) 
  {int n = height.size();vector<int> left(n, 0), right(n, 0);// 预处理left[0] = height[0];for(int i = 1; i < n; i++){left[i] = max(left[i - 1], height[i]);}right[n - 1] = height[n - 1];for(int i = n - 2; i >= 0; i--){right[i] = max(right[i + 1], height[i]);}// 求结果int ret = 0;for(int i = 1; i < n - 1; i++){ret += min(left[i], right[i]) - height[i];}return ret;
  }
  

---