排书(dfs剪枝)

排书(dfs剪枝),第1张

这个题做起来特别无语,发现自己一些正常的模拟 *** 作都需要联系

给定 n 本书,编号为 1∼n。

在初始状态下,书是任意排列的。

在每一次 *** 作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。

我们的目标状态是把书按照 1∼n 的顺序依次排列。

求最少需要多少次 *** 作。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据包含两行,第一行为整数 n,表示书的数量。

第二行为 n 个整数,表示 1∼n的一种任意排列。

同行数之间用空格隔开。

输出格式

每组数据输出一个最少 *** 作次数。

如果最少 *** 作次数大于或等于 5 次,则输出 5 or more

每个结果占一行。

数据范围

1≤n≤15

输入样例:

3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10

输出样例:

2
3
5 or more

代码:

#include
#include
using namespace std;
const int N=16;
int q[N];
int g[6][N];
int n;
int f()
{
    int tot=0;//tot用于记住每个数后缀出现错误的数
    for(int i=1;i<=n-1;i++)
        if(q[i]+1!=q[i+1])
        tot++;

    return (tot+2)/3;//因此每次交换只能改变三个后缀(假设每次都能正确改回三个)
}
bool panduan()
{
    for(int i=1;i<=n;i++)
        if(q[i]!=i)
            return false;
    return true;
}
bool dfs(int u,int depth)
{
    if(u+f()>depth)return false;//如果最优情况下,交换的已经次数都大于depth的话,直接返回false
    if(panduan())return true;//找到解后返回
    for(int len=1;len         for(int qi1=1;qi1+len-1<=n;qi1++)
    {
        int r=qi1+len;
        for(int wai=r;wai<=n;wai++)
        {
            memcpy(g[u],q,sizeof q);
            int i,j;//i用于记住每次对接的起点,j表示每次对接的长度。注意!!!

            //将某个块砍掉在接起来,一定要记住每次对接的末尾
            for(i=qi1,j=r;j<=wai;i++,j++)q[i]=g[u][j];
            for(j=qi1;j<=qi1+len-1;i++,j++)q[i]=g[u][j];
            if(dfs(u+1,depth)){
                    return true;
            }
            memcpy(q,g[u],sizeof g[u]);
        }
    }

    return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            scanf("%d",&q[i]);
        int depth=0;

        while(depth<=5&&!dfs(0,depth))
                depth++;
        if(depth<5)
            printf("%d\n",depth);
        else
            printf("5 or more");
    }

    return 0;
}
 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1295686.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存