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

本文主要是介绍[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;
}