ACM模板——排列 - 不重复全排列(DFS + 计数 + 附加规则)

简介: ACM模板——排列 - 不重复全排列(DFS + 计数 + 附加规则)

说明:不重复排列:指的是排列当中没有重复的序列,不是说里面的元素没有重复。

附加规则:针对:1 2 2 3 4 5(六个数字)

1、数字4 不能放在第三位置上。

2、数字3 和 数字5 不能相邻(不包括首尾)。

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,cnt,used[10],rcd[6],a[10];
void init()
{
    m=cnt=0;
    mem(rcd,0);
    mem(used,0);
}
void dfs(int l)
{
    if(l==n)
    {
        for(int i=0;i<n;i++)
            printf("%d ",rcd[i]);
        puts("");
        cnt++;
        return;
    }
    for(int i=0;i<m;i++)
    {
        if(used[i]>0 && !(a[i]==4&&l==2)) // used[i]还有个数 && 数字4 不能放在第三个位置上
        {
            // 数字5 和 数字3 不能相邻,不包括首尾
            if(l-1>=0&&a[i]==5&&rcd[l-1]==3 || l-1>=0&&a[i]==3&&rcd[l-1]==5)
                continue;
            used[i]--;
            rcd[l]=a[i];
            dfs(l+1);
            used[i]++;
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        int val,j;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&val);
            for(j=0;j<m;j++)
            {
                if(a[j]==val)
                {
                    used[j]++; break;
                }
            }
            if(j==m) a[m]=val,used[m++]=1;
        }
        dfs(0);
        printf("cnt == %d\n",cnt);
    }
    return 0;
}
目录
相关文章
|
5月前
|
算法 Java
力扣经典150题第二十三题:找出字符串中第一个匹配项的下标
力扣经典150题第二十三题:找出字符串中第一个匹配项的下标
26 0
|
6月前
|
人工智能 自然语言处理 算法
【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数
【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数
|
6月前
|
算法 索引 Python
如何实现二分查找算法? 要求:编写一个Python函数,输入一个有序列表和一个目标值,返回目标值在列表中的索引。如果目标值不在列表中,返回-1。
如何实现二分查找算法? 要求:编写一个Python函数,输入一个有序列表和一个目标值,返回目标值在列表中的索引。如果目标值不在列表中,返回-1。
70 0
|
存储 算法 测试技术
LeetCode算法小抄--O(1)时间下删除-查找数组中任意元素
LeetCode算法小抄--O(1)时间下删除-查找数组中任意元素
python实现将给定列表划分为元素和大致相等的两个子列表
python实现将给定列表划分为元素和大致相等的两个子列表
(二分模板边界移动写法解析)789. 数的范围
(二分模板边界移动写法解析)789. 数的范围
60 0
【那些年那些题】杨氏矩阵查找目标数
【那些年那些题】杨氏矩阵查找目标数
42 0
|
算法
【CCCC】L3-011 直捣黄龙 (30分),Dijkstra维护点权,节点数,路径条数等+路径打印
【CCCC】L3-011 直捣黄龙 (30分),Dijkstra维护点权,节点数,路径条数等+路径打印
170 0