C++ 算法学习——1.8 状态剪枝

在C++中，状态剪枝是一种优化技术，通常用于搜索算法（如深度优先搜索、广度优先搜索、回溯等）中，以减少搜索空间和提高算法效率。状态剪枝通过判断当前状态是否有必要继续搜索下去，从而避免对无效状态的搜索，节省时间和资源。

常见的状态剪枝策略：

1. 启发式函数：定义一个评估函数，根据当前状态的特征对其进行评估，以确定是否值得进一步搜索。

2. 剪枝条件：根据问题的特性确定哪些状态是无效的，可以直接跳过这些状态而不进行搜索。

3. Alpha-Beta剪枝：主要用于博弈树搜索中，通过比较已搜索到的最好结果来剪枝，避免搜索无效的分支。

4. 重复状态检测：在搜索过程中，如果出现已经搜索过的状态（局部也行），可以避免再次搜索相同的状态，从而避免无限循环。

5. 局部剪枝：在某些情况下，可以通过一些特定规则对当前状态进行局部剪枝，提前终止当前搜索路径。

P1. 洛谷p1036选数

#include<iostream>
#include<vector>
using namespace std;
int n,k;
int curnums=0;
int cursum=0;
int ans=0;bool is_primenum(int x)
{int i=2;while(i<x/2){if(x%i==0) return 0;i++;}return 1;
}void dfs(vector<int> nums,int curdex)
{curnums++;cursum+=nums[curdex];if(curnums==k){if(is_primenum(cursum)) {ans++;}curnums--;cursum-=nums[curdex];return;}for(int i=curdex+1;i<n;i++){dfs(nums,i);}curnums--;cursum-=nums[curdex];
}int main()
{cin>>n>>k;vector<int> nums;nums.resize(n,0);for(int i=0;i<n;i++) cin>>nums[i];for(int i=0;i<n-k+1;i++)dfs(nums,i);cout<<ans;return 0;
}