全排列模板

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
int n;
bool st[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++) cout<<path[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

1.带分数

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
int n;
int cnt=0;
bool st[N];

/*
    1.枚举1-9的全排列数字
    2.将全排列数字分成a、b、c三个区域
    3.判断该枚举的数组成的a、b、c是否满足等式
*/

int calculate(int l,int r)
{
    int res=0;
    for(int i=l;i<=r;i++)
        res=res*10+path[i];
    return res;
}

void dfs(int u)
{
    if(u==9)
    {   
        //将全排列数字分成a、b、c三个区域
        for(int i=0;i<7;i++)
            for(int j=i+1;j<8;j++)
            {
                int a=calculate(0,i);
                int b=calculate(i+1,j);
                int c=calculate(j+1,8);
        //判断该枚举的数组成的a、b、c是否满足等式
                if(n*c==a*c+b)//下取整不能写成n==a+b/c 
                cnt++;
            }
        return;
    }
    for(int i=1;i<=9;i++)//枚举1-9的全排列数字
    {
        if(!st[i])
        {
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;        
        }
    }
}


int main()
{
    cin>>n;
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}

2.飞机降落

#include<bits/stdc++.h>
using namespace std;
const int N=10+5;
/*
1.枚举所有的降落顺序
2.判断每一种顺序是否合法
3.当顺序确定,对于任意飞机在哪一时刻降落
*/

bool st[N];//用于标记当前飞机是否降落
int n;//飞机数量
struct plane
{
    int t,d,l;
//t表示到达时间,d表示盘旋时间,l表示降落所需时间
}p[N];

//u表示已经有u驾飞机成功降落
//time表示前一驾飞机降落的时间
bool dfs(int u,int time)
{
    if(u>=n) return true;
    for(int i=0;i<n;i++)
    {
        if(!st[i]) 
        {
            st[i]=true;
            if(p[i].t+p[i].d<time)
        //判断每一种顺序是否合法
            {
                st[i]=false;//回溯
                return false;
            }
            int t=max(p[i].t,time)+p[i].l;
            //t表示下一驾飞机降落的时间
            if(dfs(u+1,t)) return true;
            st[i]=false;//回溯
        }
    }
    return false;//上面没有一种方案合法
}
int main()
{
    int t; cin>>t;
    while(t--)
    {    
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>p[i].t>>p[i].d>>p[i].l;

        if(dfs(0,0))
            cout<<"YES"<<endl;
        else 
            cout<<"NO"<<endl;

        for(int i=0;i<n;i++)
        st[i]=false;
    //对于每组测试样例都需要重新初始化
    }
    return 0;
}

3.买瓜

#include<bits/stdc++.h>
using namespace std;
const int N=50;
const int INF=0x3f3f3f3f;//无穷大
int ans=INF;
int a[N];//原数组
double s[N];//后缀和数组
int n,m;

/*
剪枝优化减少枚举方案:
1.如果当前方案切的刀数已经大于等于先前已有的合法的最优解 return
2.如果后面的瓜的总重量再加上先前的瓜的重量都小于m return
3.如果当前已有的瓜的重量已经大于m则方案不合法 return
4.n个瓜都遍历完 return
5.贪心思想:将瓜的重量从大到小排序
*/

//u表示当前的瓜,w表示当前瓜的重量,cnt表示已经切的刀数
void dfs(int u,double w,int cnt)
{
//找到一组解
    if(w==m) 
    {
        ans=min(ans,cnt); return;
    }
//n个瓜都遍历完
    if(u>=n) return;
//当前方案切的刀数已经大于等于先前已有的合法的最优解
    if(cnt>=ans) return;
//当前已有的瓜的重量已经大于m
    if(w>m) return;
//后面的瓜的总重量再加上先前的瓜的重量都小于m
    if(w+s[u]<m) return;

    //选,但不切
    dfs(u+1,w+a[u],cnt);
    //选,并且切
    dfs(u+1,w+a[u]/2.0,cnt+1);
    //不选
    dfs(u+1,w,cnt);
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) 
        cin>>a[i];
    sort(a,a+n,greater<int>());//从大到小排序
    for(int i=n-1;i>=0;i--)
        s[i]=s[i+1]+a[i];//求后缀和
    dfs(0,0.0,0);
    if(ans==INF) ans=-1;
    cout<<ans<<endl;
    return 0;
}