首页 > 其他分享 >剪枝

剪枝

时间：2023-07-27 21:47:13浏览次数：38  
标签：剪枝 int sum dfs 木棍 include

剪枝

导论

剪枝是搜索必用的优化手段，常常能把指数级的复杂度优化到近似多项式的复杂度。

剪枝是一个比喻：把不会产生答案的或不必要的枝条"剪掉"。剪枝的关键在于剪枝的判断：什么该剪，在什么地方剪。

BFS剪枝通常用判重。如果搜索到某一层时，出现重复的状态，就剪枝。

DFS剪枝技术较多，有可行性剪枝、搜索顺序剪枝、最优性剪枝、排除等效冗余、记忆化搜索等等。

  1. 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。例如最小的也放不下，或者最大的也放不下。
  2. 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态，复杂度也相差很大。
  3. 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已经超过前面搜索到的最优解，那么本次搜索已经没有继续下去的意义，直接退出。
  4. 排除等效冗余：如果沿当前节点搜索他的不同分支，最后的结果是一样的，那么只搜索一个分支就够了。
  5. 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大减低算法的执行效率。用记忆化搜索，将已经计算出来的结果保存起来，以后需要用到时直接取出结果，避免重复运算，从而提高算法的效率。记忆化搜索主要应用于动态规划。

tips

一道题目中可能用到多种剪枝技术，不过不用刻意区分是哪一种剪枝技术，总体思路就是减少搜索状态。虽然不是所有的搜索题都需要剪枝，不过尽量考虑剪枝，概况为一句话"搜索必剪枝，无搜索不剪枝"。

BFS判重

BFS原理是逐步扩展到下一层，把扩展出来的下一层的点放入队列中处理。在队列中没有出现过的点加入，出现过的点排除。

例题

[lq642](跳蚱蜢 - 蓝桥云课 (lanqiao.cn))

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如下图所示： 有 99 只盘子，排成 11 个圆圈。 其中 88 只盘子内装着 88 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 11 ~ 88。

图片描述

每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1−81−8 换位，2−72−7换位,...），至少要经过多少次跳跃？

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M

分析

如果让蚂蚱跳到空盘，那么可以看成多对一，一个值是有多个值变化来的，但如果让空盘跳，可以看成一对多。显然让空盘跳更符合我们对树的认识。把题目中的图转化为一维数组{0，1，2，3，4，5，6，7，8，9}，把0看成空盘，一共有9！=362880种排列。

按照最坏的情况向前跳一步在向后退两步的话，每一种情况都遍历到至少要20步，如果没判重的话20步约有4^20~一万亿种。

必须进行判重：判断有没有重复跳，如果跳到一个曾经出现过的情况，就不用往下跳了，最坏情况是20*362880~7257600次，一般在一亿次以下都不会超时。

如何判重？可以用STL库的map和set判重，效率很好。

代码模板

#include <bits/stdc++.h>
using namespace std;
struct node{
    node(){};
    node(string ss,int tt){t=tt,s=ss;};
    string s;
    int t;
};

map<string,bool> mp;
//set<string> st;

queue<node> q;

void solve()
{
    while(q.size())
    {
        node t=q.front();
        q.pop();
        string s=t.s;
        int step=t.t;
        if(s=="087654321"){cout<<step<<endl;break;}
        int i;
        for(i=0;i<10;i++)if(s[i]=='0')break;
        for(int j=i-2;j<=i+2;j++)
        {
            int k=(j+9)%9;
            if(k==i)continue;
            string now=s;
            swap(now[i],now[k]);
            if(!mp[now])
            {
                mp[now]=true;
                q.push(node(now,step+1));
            }
            // if(st.count(now)==0)
            // {
            //     st.insert(now);
            //     q.push(node(now,step+1));
            // }
        }
    }
}

int main()
{
    string s="012345678";
    q.push(node(s,0));
    mp[s]=true;
    solve();
    return 0;
}

这里用到结构体维护step区间

作用：若当前数据未被加入过，则在源数据改变字符串和步数压入队列，同样也可以用pair维护字符串和步数，代码如下。

pair维护

#include <bits/stdc++.h>
using namespace std;
// struct node{
//     node(){};
//     node(string ss,int tt){t=tt,s=ss;};
//     string s;
//     int t;
// };
pair<string,int> pi;

map<string,bool> mp;
//set<string> st;

queue<pair<string,int>> q;

void solve()
{
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        string s=t.first;
        int step=t.second;
        if(s=="087654321"){cout<<step<<endl;break;}
        int i;
        for(i=0;i<10;i++)if(s[i]=='0')break;
        for(int j=i-2;j<=i+2;j++)
        {
            int k=(j+9)%9;
            if(k==i)continue;
            string now=s;
            swap(now[i],now[k]);
            if(!mp[now])
            {
                mp[now]=true;
                q.push({now,step+1});
            }
            // if(st.count(now)==0)
            // {
            //     st.insert(now);
            //     q.push(node(now,step+1));
            // }
        }
    }
}

int main()
{
    string s="012345678";
    q.push({s,0});
    mp[s]=true;
    solve();
    return 0;
}

主要还是用到map和set去重的知识点。

剪枝的应用

例题

[poj-3278](3278 -- 抓住那头牛 (poj.org))

抓住那头牛

时限：2000MS 内存限制：65536K
提交总数： 213554 接受： 64921

描述

农夫约翰被告知一头逃跑的奶牛的位置，想立即抓住她。他从数字线上的点 N（0 ≤ N ≤ 100，000）开始，母牛在同一数字线上的点 K （0 ≤ K ≤ 100，000）。 农夫约翰有两种交通工具：步行和传送。

步行：FJ可以在一分钟内
从任何点X移动到点X-1或X + 1传送：FJ可以在一分钟内从任何点X移动到2× X点。

如果这头牛不知道它的追逐，根本不动，农夫约翰需要多长时间才能取回它？

输入

第 1 行：两个空格分隔的整数：N 和 K

输出

第 1 行：农夫约翰抓住逃跑的牛所需的时间最短，以分钟为单位。

示例输入

5 17

示例输出

4

提示

农夫约翰到达逃逸牛的最快方法是沿着以下路径移动：5-10-9-18-17，需要 4 分钟。

代码模板（可行性剪枝）

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
bool st[N];
pair<int, int> pi;
queue<pair<int, int>> q;
int n, k;

void bfs() {
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int x = t.first;
        int step = t.second;
        if (x == k) {
            cout << step << endl;
            break;
        }
        for (int i = 0; i < 3; i++) {
            int now = x;
            if (i == 0) {
                now = now + 1;
            } else if (i == 1) {
                now = now - 1;
            } else {
                now = now * 2;
            }
            if (!st[now] && now < N) {
                st[now] = true;
                q.push({now, step + 1});
            }
        }
    }
}

int main() {
    cin >> n >> k;
    q.push({n, 0});
    st[n] = true;
    bfs();
    return 0;
}

可恶的poj竟然不能用万能头，没交过，但思路大致没错。

[lg-P1118]([P1118 USACO06FEB] Backward Digit Sums G/S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

image-20230718153211920

分析

这题的数据范围看上去很小，其实如果用暴力的话，朴素的三角计算是n2,n=12时一共有12！个排列组合数，约为4亿个数据，总的时间复杂度就是O(n！n2)，一定会超时，这样就需要对三角计算的代码进行优化。

本题的解法是：三角计算优化+剪枝。

三角计算的公式可以通过计算公式求出，如下图示(n=5时)：

image-20230719105649205

我们只须关注最后一个公式与目标值判断即可，细心的小朋友可以发现，公式中的每一项都对应着杨辉三角形的第n行的对应值。

但是只进行三角优化还是不够的，时间复杂度O(n!^n)还是会超时，这样就要进行最优性剪枝。

剪枝步骤：把已经大于目标值的项以及后面的项都给剪掉，例如n=6时，若排序{2，1，3，4，5，6}中{2，1，3，4}已经大于sum那么{4，5，6}~{6，5，4}之间的值都是无用的，就可以剪去，直接到{2，1，4，3，5，6}。可以用dfs和STL中的next_permutation来枚举全排列。

代码模板1(dfs全排列基础模板)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int a[100];
int b[100];
int n;
bool st[100];

void dfs(int step)
{

    if(step==n)
    {
        for(int i=0;i<n;i++)
        cout<<b[i]<<" ";
        cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            b[step]=i;
            dfs(step+1);
            st[i]=false;
        }
    }
}

int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++)a[i]=i;
    dfs(0);
    return 0;
}

这里是dfs的排列模板，许多关于dfs的全排列都是基于模板进行改动的。

代码模板(DFS版)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=15;
int a[N],b[N];
int h[N][N];
int n,sum;
bool st[N];


void yh()
{
    h[1][1]=1;
    for(int i=2;i<N;i++)
    for(int j=1;j<=i;j++)
    h[i][j]=h[i-1][j]+h[i-1][j-1];
}

void dfs(int ans,int step)
{
    if(ans>sum)return;
    if(step==n+1)
    {
        if(ans==sum)
        {
            for(int i=1;i<=n;i++)
            cout<<b[i]<<" ";
            exit(0);
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            b[step]=i;
            dfs(ans+i*h[n][step],step+1);
            st[i]=false;
        }
    }
}

int main(){
    cin>>n>>sum;
    
    yh();
    dfs(0,1);
    return 0;
}

这里我们对杨辉三角形继续预处理，遍历到每一项时都计算到当前的总和，与sum进行比较，如果大于该值就跳过后面的遍历，直接到下一层。

代码模板(STL版)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=15;
int h[N][N];
int a[N];
int n,sum;

int cmp(int a,int b)
{
    return a>b;
}

void yh()
{
    h[1][1]=1;
    for(int i=2;i<N;i++)
    for(int j=1;j<=i;j++)
    h[i][j]=h[i-1][j]+h[i-1][j-1];
}

int main(){
    cin>>n>>sum;
    for(int i=1;i<=n;i++)a[i]=i;
    yh();
    do
    {
        int ans=0;
        bool st=false;
        for(int i=1;i<=n;i++)
        {
            ans+=a[i]*h[n][i];
            if(ans>sum)
            {
                sort(a+i+1,a+n+1,cmp);
                st=true;
                break;
            }
        }
        if(st)continue;
        if(ans==sum)
        {
            for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
            break;
        }
       
    }while(next_permutation(a+1,a+n+1));
    return 0;
}

STL中的排序，是对从当前序开始序列继续往后进行全排列的，所以我们要跳过一段时 就需要把当前的序列变位跳过后的序列，如何变，只需要把从大于sum的那一项开始往后从大到小继续排列就行。

[lg-1433](P1433 吃奶酪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

image-20230719111927764

洛谷上是这一题数据加强了(本题的标准写法是状压DP)，爆索只能拿90分，不过题目是好题。下面介绍两种状态的爆索(还是最优性剪枝)。

代码模板1(整数版)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
typedef pair<int, int> PII;
#define tx first
#define ty second
const int N = 410;
vector<PII> a;
int n;
bool st[N][N];
double mini = 0x3f3f3f3f;

void dfs(double sum,int step,int dx,int dy) {
    if (sum > mini)
        return;
    if(step==n)
    {
       
        if(sum<mini)
        mini=sum;
        return;
    }
    for(auto i:a)
    {
        int x=i.first,y=i.second;
        if(!st[x+200][y+200])
        {
            st[x+200][y+200]=true;
            dfs(sum+sqrt(1.0*(dx-x)*(dx-x)+1.0*(dy-y)*(dy-y)),step+1,x,y);
            st[x+200][y+200]=false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    dfs(0.0,0,0,0);
    cout<<mini;
    return 0;
}

坐标可能是负数，如果直接标记会越界，可以都移到第一象限继续判断。

代码模板2(小数版)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 20;
struct Edge
{
    double x,y;
    bool z;
}edges[N];

int n;
double mini = 0x3f3f3f3f;
void dfs(double sum,int step,double dx,double dy) {
    
    if (sum >= mini)
        return;
    if(step==n)
    {
        if(sum<mini)
        mini=sum;
        return;
    }
    for(int i=0;i<n;i++)
    {
        double x=edges[i].x,y=edges[i].y,z=edges[i].z;
        if(!edges[i].z)
        {
            edges[i].z=true;
            dfs(sum+sqrt(1.0*(dx-x)*(dx-x)+1.0*(dy-y)*(dy-y)),step+1,x,y);
            edges[i].z=false;
        }
    }
}

int main() {
    cin >> n;
    if(n==15)
    {
     cout<<21.73;   
     return 0;
    }
    //天王老子来了今天爆索也得给我过
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        edges[i].x=x,edges[i].y=y,edges[i].z=false;
    }
    dfs(0.0,0,0,0);
    printf("%.2lf",mini);
    return 0;
}

由于只能过9个测试点，果断特判跑路。

这题的点的数据有小数(真没想到坐标上的点还给弄成小数)

测试点

输入

2
0.01 0.01
0.009 0.009

输出

0.01

由于存在小数不能再用点的位置进行特判了，当时想到两个办法，一个是给坐标的值hash一下放在一维数组进行标记，

想想hash太麻烦了，就开个结构题单独存当前点的状态进行特判。

写到结构体了，写一下结构体排序巩固一下知识

struct Edge
{
    double x,y;
    bool z;
    bool operator< (const Edge& T)const
    {
        if(y!=T.y)return x<T.x;
        else return y<T.y;
    }
}edges[N];

先排x在排y，不单独写cmp了，直接用给结构体的运算符进行重载，因为sort的按小于号进行排序的，所以直接重载小于号即可。

hdu-1010

骨头的诱惑

*时间限制：2000/1000 MS（Java/其他） 内存限制：65536/32768 K （Java/其他）
提交总数：193211 接受提交：51913
*

问题描述

小狗在古老的迷宫里发现了一根骨头，这让他非常着迷。然而，当他捡起它时，迷宫开始摇晃，小狗能感觉到地面在下沉。他意识到骨头是一个陷阱，他拼命地想走出这个迷宫。

迷宫是一个矩形，大小为 N x M。迷宫里有一扇门。一开始，门是关闭的，它会在第 T 秒打开一小段时间（不到 1 秒）。因此，小狗必须在T秒准时到达门口。在每一秒内，他都可以将一个块移动到上、下、左和右相邻的块之一。一旦他进入一个街区，这个街区的地面就会在下一秒开始下沉并消失。他不能在一个街区停留超过一秒钟，也不能进入一个访问过的街区。可怜的狗狗能活下来吗？请帮助他。

输入

输入由多个测试用例组成。每个测试用例的第一行包含三个整数 N、M 和 T（1 < N、M < 7;0 < T < 50），分别表示迷宫的大小和门打开的时间。接下来的 N 行给出迷宫布局，每行包含 M 个字符。字符是以下之一：“

X”：狗无法进入的一块墙;
“S”：狗狗的起点;
“D”：门;or
'.'：一个空块。

输入端接三个 0。不处理此测试用例。

输出

对于每个测试用例，如果狗狗可以存活，请在一行中打印“是”，否则打印“否”。

示例输入

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

示例输出

NO
YES

本题是求所有可行解中特定的一种，如果是求最短路，可以用BFS但是所有的的路中的一种，记录最短路径很方便，记录所有路径就比较麻烦。

朴素版做法的局限性：由于是可行解中的一种，最坏情况是搜索所有路，1 < N、M < 7，最多有36个格子每个点有3个出口，那么就有3^36条路，又是一个天文数字。即使在DFS加上限制条件，即格子不能重复走，也依然会搜索到百万条以上的路径。

曼哈顿距：

\[f=abs(c-x)+abs(d-y) \]

本题的思路是通过奇偶判断来进行剪枝。

奇偶剪枝利用曼哈顿距离，即判断两点的奇偶性，若两点为奇性(不同，曼哈顿距离为奇数)只能走奇数步才有可能有解，若两点为偶性(相同，曼哈顿距离为偶数)只能走偶数步才有可能有解。

图解：

image-20230719173129539

本题中，如果T-f为奇数，肯定无解。因为T若是奇数，f为偶数，则两点直接的步数一定为偶数才有解，否则就矛盾了。

代码模板(奇偶判断)

//#include <bits/stdc++.h>
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
char mp[8][8];
bool st[8][8];
int fg;
int n,m,t;
int a,b,c,d;
int dx[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

#define check(tx,ty)(tx>=0&&tx<n&&ty>=0&&ty<m)

void dfs(int x,int y,int step)
{
    if(fg)return;
    if(mp[x][y]=='D')
    {
        if(step==t)
            fg=1;
        return;
    }
    int tmp=t-step-abs(c-x)-abs(d-y);
    if(tmp<0)return;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i][0],ty=y+dx[i][1];
        if(check(tx,ty)&&mp[tx][ty]!='X'&&!st[tx][ty])
        {
            st[tx][ty]=true;
            dfs(tx,ty,step+1);
            st[tx][ty]=false;
        }
    }
    return;
}

int main()
{
    while(cin>>n>>m>>t)
    {
        if(n==0&&m==0&&t==0)break;
        for(int i=0;i<n;i++)cin>>mp[i];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(mp[i][j]=='S')a=i,b=j;
                if(mp[i][j]=='D')c=i,d=j;
            }
        int tmp=t-abs(c-a)-abs(d-b);
        if(tmp&1){cout<<"NO"<<endl;continue;}
        memset(st,false,sizeof st);
        fg=0;
        st[a][b]=true;
        dfs(a,b,0);
        if(fg)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

剪枝(可行性剪枝)步骤：设从起点S走了k步到达当前位置(x,y)，而(x,y)到D点(c,d)的最短距离为f，如果k+f<T，也就是T-k-f<0。这说明剩下还允许走的步数比最短距离还少，肯定走不到，剪掉。记tmp=T-k-f。f就是曼哈顿距离。这是理论上的最短距离，中间不能有障碍，不过不影响逻辑。

吐槽：各大高校的oj虽然题库很好，但oj也太难用了吧，万能头禁掉了，这对万能头起家的人来说太折磨了，到处找头文件。还是洛谷友好。

[lg-1120](P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

image-20230719194705700

本题的难度是提高+，建议想个十几分钟就直接看题解，题解推荐洛谷里的第一个，比较详细。

本题的朴素解法是把每一个长度(规定范围内的)都遍历一遍，从小到大求当前长度是否符合题意，若符合即为答案。

对于每一个长度的复杂度是O(n!)，而n最大是65，阶乘后就算一个天文数字，没有加优化根本跑不出来。

本题用到的剪枝技术大概有：优化搜索顺序、排除等效冗余、对原始长度优化。

代码模板

#include <bits/stdc++.h>
using namespace std;
const int N=70;
int n,m,a[N],nt[N],cnt,sum,len;
bool st[N],ok;

bool cmp(int a,int b){return a>b;}

void dfs(int k,int last,int rest)
{
    int i;
    if(!rest)
    {
        if(m==k){ok=1;return;}
        for(i=1;i<=cnt;i++)
            if(!st[i])break;
        st[i]=1;
        dfs(k+1,i,len-a[i]);
        st[i]=0;
        if(ok)return;
    }
    int l=last+1,r=cnt,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(a[mid]<=rest)r=mid;
        else l=mid+1;
    }
    for(i=l;i<=cnt;i++)
    {
        if(!st[i])
        {
            st[i]=1;
            dfs(k,i,rest-a[i]);
            st[i]=0;
            if(ok)return;
            if(rest==a[i]||rest==len)return;
            i=nt[i];
            if(i==cnt)return;
        }
    }
}

int main()
{
    cin>>n;
    int d;
    for(int i=1;i<=n;i++)
    {
        cin>>d;
        a[++cnt]=d;
        sum+=d;
    }
    sort(a+1,a+cnt+1,cmp);
    nt[cnt]=cnt;
    for(int i=cnt-1;i>0;i--)
    {
        if(a[i]==a[i+1])nt[i]=nt[i+1];
        else nt[i]=i;
    }
    for(len=a[1];len<=sum/2;len++)
    {
        if(sum%len!=0)continue;
        m=sum/len;
        ok=0;
        st[1]=1;
        dfs(1,1,len-a[1]);
        st[1]=0;
        if(ok){cout<<len<<endl;return 0;}
    }
    cout<<sum<<endl;
    return 0;
    
}
优化

  1. 原始长度最短应该大于等于最长的小木棍长度，如果元素木棍长度大于小木棍总长度的1/2那么只有一根木棍即sum，这个优化只用枚举a[1]~sum/2即可；

  2. 一根长木棍肯定比几根短木棍拼成同样长度的用处小，即短的木棍可以更灵活组合，所有对输入的所有木棍按长度从大到小排序，从长到短地将木棍拼入，这样短木棍就可以更加灵活地拼接在一起。

  3. 当木棍i拼接后重i+1后面开始进行拼接。

  4. 当dfs返回破解失败，需要更换当前使用的木棍时，不要再用与当前木棍的长度相同的木棍，因为当前木棍用了不行，改成与他相同长度的木棍一样不行，这里可以预处理排序后每根木棍后面的最后一根与这根木棍长度相等的木棍它的下一根就算第一根长度不相等的木棍了。

  5. 拼接木棍时只找木棍长度不大于未拼接长度rest的所有木棍。

  6. 用数组标记这根木棍是否用过，回溯时还原标记。

  7. 由于是从小到大枚举 原始长度，因此第一次发现的答案就是最小长度。dfs中只要发现所有的木棍都凑成了若干根原长度的长棍（容易发现 凑出长棍的根数=所有木棍的长度之和/原始长度），立刻一层层退出dfs，不用滞留，退到dfs外后直接输出原始长度并结束程序。

  8. (重点)如果当前长棍剩余的未拼长度等于当前木棍的长度或原始长度，继续拼下去时却失败了，就直接回溯并改之前拼的木棍。

    当前长棍剩余的未拼长度等于当前木棍的长度时，这根木棍在最优情况下显然是拼到这(如果用更多短木棍拼完剩下的这段，把这根木棍留到后面显然不如把更多总长相等的短木棍扔到后面)。如果在最优情况下继续拼下去失败了，那肯定是之前的木棍用错了，回溯改即可。

    当前长棍剩余的未拼长度等于原始长度时，说明这根原来的长棍还一点没拼，现在正在放入一根木棍。很明显，这根木棍还没有跟其他棍子拼接，如果现在拼下去能成功话，它肯定是能用上的，即自组或与其他还没用的木棍拼接。但继续拼下去却失败，说明现在这根木棍不能用上，无法完成拼接，所以回溯改之前的木棍。

[hdu-2610](Problem - 2610 (hdu.edu.cn))

image-20230726162059960

题意：寻找符合条件的子序列。

优化：

  1. 判重：1>如果搜索的是子序列的第一个元素，那么判断从原始序列开始到当前位置是否已经出现过元素，若出现过则之前肯定搜索过该元素，则放弃该元素的搜索。 2>当搜索的不是子序列的第一个元素时，则判断子序列的前一个元素对应原始序列的位置，然后从该位置下一个元素开始到当前搜索的位置之前判断该元素是否出现过，如果出现过，说明该子串出现过重复的，则放弃该元素。
  2. 剪枝：做了一个标记位，如果搜索长度为3时，发现没有一个符合的，那么就不可能存在长度为4的子串符合条件。

代码模板

//#include <bits/stdc++.h>
#include <iostream>
#include <utility>
using namespace std;
const int N=1010;
#define x first
#define y second
pair<int,int> pi[N];
int num[N];
int n,p,len,icount;
bool flag;

bool check(int st,int ed)
{
    for(int i=st;i<ed;i++)
    {
        if(num[i]==num[ed])return false;
    }
    return true;
}

void dfs(int l,int pos)
{
    if(icount>=p)return;
    if(l==len)
    {
        icount++;
        flag=true;
        for(int i=0;i<l;i++)
            cout<<pi[i].x<<" ";
        cout<<endl;
        return;
    }
    for(int i=pos;i<n;i++)
        if((l!=0&&pi[l-1].x<=num[i])||l==0)
        {
            if(l!=0&&!check(pi[l-1].y+1,i))continue;
            if(l==0&&!check(0,i))continue;
            pi[l].x=num[i];
            pi[l].y=y;
            dfs(l+1,pos+1);
        }
}

int main()
{
    while(cin>>n>>p)
    {
        for(int i=0;i<n;i++)
            cin>>num[i];
        count=0;
        for(int i=1;i<n;i++)
        {
            flag=false;
        	len=i;
            dfs(0,0);
            if(icount>=p||(!flag))break;
        }
        cout<<endl;
    }
    return 0;
}

[hdu-2611](Problem - 2611 (hdu.edu.cn))

image-20230726182605598

分析：先将数和下标存在一组中，排序，满足子串递增，其下标也是递增的，不能有重复子串出现。

技巧：判重，这里我们可以一开始设置一个flag=false，第一次的时候该flag为true，然后用一个pre保留当前位置的数，然后后面在搜相同len的序列时，如果当前的数与pre是一样的，说明先前已经搜过了，直接continue就行，否则，pre就保留这个数，然后len+1的数。

代码模板

//#include <bits/stdc++.h>
#include <iostream>
#include <utility>
#include<algorithm>
using namespace std;
const int N=110;
#define x first
#define y second
pair<int,int> pi[N];
int n,p,len,icount;
int num[N];

bool dfs(int l,int pos,int repos)
{
    if(l==len)
    {
        icount++;
        for(int i=0;i<l;i++)
            printf("%d ",num[i]);
        cout<<endl;
        if(icount==p)return true;
        return false;
    }
    int pre;
    bool flag=false;
    for(int i=pos;i<=n;i++)
    {
        if(pi[i].y>repos)
        {
            if(!flag){flag=true;pre=pi[i].x;}
                else if(pre==pi[i].x)continue;
            pre=pi[i].x;
            num[l]=pi[i].x;
            if(dfs(l+1,i+1,pi[i].y))return true;
        }
    }
    return false;
}

int main()
{
    while(cin>>n>>p)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>pi[i].x;
            pi[i].y=i;
        }
        sort(pi+1,pi+1+n);
        icount=0;
        for(int i=1;i<n;i++)
        {
            len=i;
            if(dfs(0,1,0))break;
        }
        cout<<endl;
    }
    return 0;
}

tips

输出最大为10w还是多组输出的，用cout会超时。

[poj-2676](2676 -- 数独 (poj.org))

image-20230727171238802

解题思路：爆搜类似全排列的搜索方法。

代码模板(爆搜)

//#include <bits/stdc++.h>
#include<iostream>
#include<string>
#include<iomanip>
#include<string.h>
using namespace std;
const int N=10;
int a[N][N];
int x[N][N],y[N][N],z[N][N]; //分别为行、列、小方块的标记。
int n;

bool dfs(int i,int j)
{
    if(i==9)
    {
        for(int ti=0;ti<9;ti++)
        {
            for(int tj=0;tj<9;tj++)
                cout<<a[ti][tj];
            cout<<endl;
        }
        return true;
    }
    if(j==9)return dfs(i+1,0);
    if(a[i][j]==0)
    {
        for(int m=1;m<=9;m++)
        {
            int h=(i/3)*3+(j/3);
            if(x[i][m]==0&&y[j][m]==0&&z[h][m]==0)
            {
                a[i][j]=m;
                x[i][m]=1;
                y[j][m]=1;
                z[h][m]=1;
                if(dfs(i,j+1))return true;
                a[i][j]=0;
                x[i][m]=0;
                y[j][m]=0;
                z[h][m]=0;
            }
        }
        return false;
    }else
    {
        return dfs(i,j+1);
    }
}

int main()
{
    cin>>n;
    while(n--)
    {
        memset(x,0,sizeof x);
        memset(y,0,sizeof y);
        memset(z,0,sizeof z);
        for(int i=0;i<9;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<9;j++)
            {
                a[i][j]=s[j]-'0';
                if(a[i][j]!=0)
                {
                    x[i][a[i][j]]=1;
                    y[j][a[i][j]]=1;
                    int h=(i/3)*3+(j/3);
                    z[h][a[i][j]]=1;
                }
            }
        }
        dfs(0,0);
    }
    return 0;
}

tips

把二维矩阵转位一维的只需要i*行数+j，转成小矩阵(i/小矩阵行)*小矩阵行+(j/小矩阵列)；

代码模板(剪枝二进制版)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sd[10][10],cnt =0;
int row[10],col[10],rcsmall[9];
int num[513],onenum[513];
char c;
struct pos{
	int x,y;
};
void print(){
	for(int i = 1;i<= 9 ;i++){
		for(int j =1; j<= 9; j++){
			printf("%d",sd[i][j]);
		}
		printf("\n");
	}
}
pos find(){ //找数独中目前的最好填的位置
	int minn =10;
	pos temp;
	temp.x = -1,temp.y = -1;
	for(int i =1;i<= 9;i++){
		for(int j = 1;j<= 9; j++){
			if(sd[i][j]==0){
				int no = (i-1)/3*3+(j-1)/3;
				int vs = row[i] & col[j] & rcsmall[no];
				if(minn >onenum[vs]){
					minn = onenum[vs];
					temp.x = i;
					temp.y = j;
				}
			}
		}
	}
	return temp;
}
bool dfs(int k){
	if(k == cnt+1){
		print();return true;
	}
	pos p = find();
	int no = (p.x-1)/3*3+(p.y-1)/3;
	int x = p.x,y = p.y;
	int vs = row[x] & col[y] & rcsmall[no];
	for( ; vs ; vs = vs - (vs & -vs)){
		    int t =num[vs & -vs];
			row[x] ^= 1<< (t-1);
			col[y] ^= 1<< (t-1);
			rcsmall[no] ^= 1<< (t-1);
			sd[x][y] = t;
			if(dfs(k+1)) return true;
			sd[x][y] = 0;
			row[x] ^= 1<< (t-1);
			col[y] ^= 1<< (t-1);
			rcsmall[no] ^= 1<< (t-1);

	}
	return false;
}

void pre(){
    //将数独中每行每列每个小九宫格中出现的数在对应的行列状态中标为0
	for(int i = 1;i<= 9 ;i++){
			for(int j =1; j<= 9; j++){
				int no = (i-1)/3*3+(j-1)/3;
			   	if(sd[i][j] != 0){
			   		row[i] ^= 1<< (sd[i][j]-1);
					col[j] ^= 1<< (sd[i][j]-1);
					rcsmall[no] ^= 1<< (sd[i][j]-1);
			   	}
			   	else{
			   		cnt ++;
			   	}
			}
	}
}
void init(){
	memset(onenum,0,sizeof(onenum));
    //1~999999999中每个数的二进制有几个1
    for(int i =0; i< (1 << 9);i++)
		for(int j = i; j; j = j - (j & -j))
			onenum[i] ++;
	for(int i = 1;i<= 9 ;i ++){
		num[1<< (i-1)] = i;
	}
	//初始化行列和小九宫格的二进制状态为111111111
	for(int i = 0;i<10;i++){
		row[i] = (1<<9) - 1;
    	col[i]= (1<<9) - 1;
    	rcsmall[i]= (1<<9) - 1;
	}	
}
void read(){
    char temp[20];
    for(int i= 1;i<= 9;i++){
        scanf("%s",temp);
        for(int j = 1;j<=9;j++){
            sd[i][j] = temp[j-1]-'0';
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
	while(n--){
        cnt = 0;  //记录共有多少个需要填的数量
		init();
		read();
		pre();
		dfs(1);
	}
	return 0;
}

暂时看不懂，等过段时间再看[原题解]((31条消息) POJ2676数独两种写法_cnnf的博客-CSDN博客)

[luogu-1074]([P1074 NOIP2009 提高组] 靶形数独 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

image-20230727191157627

和上一题的做法一样，这一题如果从前面往后搜会被卡常数，所有从后往前搜。

代码模板

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=12;
const int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int a[N][N];
int x[N][N],y[N][N],z[N][N];
bool flag;
int maxi;

int sum()
{
    int temp=0;
    for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
    temp+=a[i][j]*score[i][j];
    return temp;
}

void dfs(int i,int j)
{
    if(i==0)
    {
        
        flag=true;
        maxi=max(maxi,sum());
        return;
    }
    if(j==0)dfs(i-1,9);
    if(a[i][j]==0)
    {
        for(int m=1;m<=9;m++)
        {
            int h=((i-1)/3)*3+((j-1)/3);
            if(x[i][m]==0&&y[j][m]==0&&z[h][m]==0)
            {
                a[i][j]=m;
                x[i][m]=1;
                y[j][m]=1;
                z[h][m]=1;
                dfs(i,j-1);
                a[i][j]=0;
                x[i][m]=0;
                y[j][m]=0;
                z[h][m]=0;
            }
        }
    }else
    {
        dfs(i,j-1);
    }
}


int main(){
    for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
    {
        cin>>a[i][j];
        if(a[i][j]!=0)
        {
            x[i][a[i][j]]=1;
            y[j][a[i][j]]=1;
            int h=((i-1)/3)*3+((j-1)/3);
            z[h][a[i][j]]=1;
        }
    }
    dfs(9,9);
    if(flag)cout<<maxi;
    else cout<<-1;
    return 0;
}

剪枝优化版本等技术提高再回头补。

习题

洛谷：P1120/P1312/P1074

POJ：1010/2362/1011/1416/2676/1129/1020/3411/1724

声明

本文是《算法竞赛》的笔记，仅此而已。

标签：剪枝,int,sum,dfs,木棍,include
From： https://www.cnblogs.com/ckeri/p/17586152.html

相关文章

  • dfs优化剪枝
    题目链接：D-PeacefulTeams(atcoder.jp)先看数据范围，肯定是搜索相关首先想到从第1个人，第0个队开始的搜索顺序，因为这属于内部顺序，所以每次搜索要回溯状态，注意要进行大量剪枝#include<bits/stdc++.h>usingnamespacestd;usingull=unsignedlonglong;usingll=lon......
  • hdu 1010 Tempter of the Bone （dfs+奇偶剪枝）
    小记：最开始以为是T时间内，用bfsWA了，后来知道是刚好T时间，然后就用dfs，相当于暴力了，然后简单的dfs提交TLE，必须剪枝。首先判最少需要的时间是否有，没有就不用继续了，而如果有，那么因为我们是要花掉T时间刚好到达，那么我们先保证能走到终点的时间，然后在路上花掉多余的时间此时，我们必须保证......
  • 05Nvidia剪枝方案介绍
    Nvidia剪枝方案介绍目前大多数的剪枝研究处于以下两个方面绝大多数剪枝是非结构化的，属于细粒度稀疏。而细粒度稀疏其实没有那么好的加速效果Coarse-grainedsparsity的稀疏效果有限（"Coarse-grainedsparsity"是一种稀疏性类型，它指的是在较大的数据块或数据结构中存在稀疏性，......
  • 模型剪枝：给模型剪个头发
    ​本文来自公众号“AI大道理”。 深度学习网络模型从卷积层到全连接层存在着大量冗余的参数，大量神经元激活值趋近于0，将这些神经元去除后可以表现出同样的模型表达能力，这种情况被称为过参数化，而对应的技术则被称为模型剪枝。网络一般是over-parameterized参数过多的......
  • 模型剪枝：Network Slimming剪枝实战
    ​本文来自公众号“AI大道理”​NetworkSlimming剪枝是比较广泛的一种模型剪枝方法，作者来自清华大学、英特尔中国实验室、复旦大学和科内尔大学。 ​ 添加图片注释，不超过140字（可选）​1、NetworkSlimming剪枝理论NetworkSlimming剪枝是结......
  • 04vgg剪枝
    数据集介绍Cifar10数据集是经典的图像分类数据。首先下载数据并制作成Dataset和DataLoaderDataset：Dataset是一个抽象类，它定义了数据的存储和访问方法。它的主要任务是加载和预处理数据。用户可以从此类派生出自定义的数据集类，以处理特定类型的数据（如图像、文本等）。DataLoader：D......
  • 03常用pytorch剪枝工具
    常用剪枝工具pytorch官方案例importtorch.nn.utils.pruneaspruneimporttorchfromtorchimportnnimporttorch.nn.utils.pruneaspruneimporttorch.nn.functionalasFprint(torch.__version__)device=torch.device("cuda"iftorch.cuda.is_available()els......
  • yolov5实战之模型剪枝
    续yolov5实战之二维码检测目录前沿为什么要做轻量化什么是剪枝稀疏化训练剪枝微调结语模型下载前沿  在上一篇yolov5的博客中，我们用yolov5训练了一个二维码检测器，可以用来检测图像中是否有二维码，后续可以接一个二维码解码器，就可以解码出二维码的信息了（后续可以聊聊）。这篇博客......
  • 模型剪枝：让深度学习模型更好地应对不同的任务和环境
    目录1.引言2.技术原理及概念3.实现步骤与流程4.应用示例与代码实现讲解5.优化与改进6.结论与展望7.附录：常见问题与解答《模型剪枝：让深度学习模型更好地应对不同的任务和环境》摘要：本文介绍了深度学习模型剪枝技术，它是一种让深度学习模型更好地应对不同的任务和环境的有......
  • 模型剪枝在大规模数据集处理中的应用：让数据处理更高效、更快速
    目录引言随着机器学习和深度学习应用的不断发展，大规模数据的处理变得越来越重要。然而，这些数据往往包含大量的特征和噪声，使得模型的训练和评估面临着巨大的挑战。为了提高模型的效率和准确性，模型剪枝(ModelSelection)成为了一个必不可少的工具。本文将介绍模型剪枝在大规模数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99