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;
}