AcWing 180. 排书
原题链接
中等
作者:
lqmm1
,
2021-12-05 23:42:25
,
所有人可见
,
阅读 529
/*
IDA*这个算法的思想其实比A*要好理解很多
简单来说就是我们开一个估计函数这个估计函数的返回值一定比真实值要小于等于这样我们就可以利用这个进行最优化减枝
如果估计函数都无法完成那么真实值一定也无法完成可以直接剪掉
这题由于步数很小答案可能会很大所以我们再用一下之前讲的迭代加深的思想来优化一下搜索
这题我们搜索可以去枚举我们选择的长度以及我们放的位置去搜索
这题我们其实可以不用往前放因为我们往前放会对应前面的一种选法完全没有必要
这题由于每次我们最多改变3个位置的关系所以假设我们有k个错误前后关系那么(k+2)/3就是我们最多要操作的次数
可以看到估计函数的影子了所以我们这题再用IDA*来优化
我们可以用这个(k+2)/3来当成估计函数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
const int N = 30;
int di[10][N];
int qi[N];
int n;
int f()
{
int cnt=0;
for(int i=1;i<=n-1;i++)
{
if(qi[i]+1!=qi[i+1])cnt++;
}
return (cnt+2)/3;
}
bool check()
{
for(int i=1;i<=n-1;i++)
{
if(qi[i]+1!=qi[i+1])return false;
}
return true;
}
bool dfs(int u,int depth)
{
if(u+f()>depth)return false;
if(check())return true;
for(int len=1;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for(int k=j+1;k<=n;k++)
{
int y=i;
memcpy(di[u+1],qi,sizeof qi);
for(int d=j+1;d<=k;d++,y++)
{
qi[y]=di[u+1][d];
}
for(int d=i;d<=j;d++,y++)
{
qi[y]=di[u+1][d];
}
if(dfs(u+1,depth))return true;
memcpy(qi,di[u+1],sizeof qi);
}
}
}
return false;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> qi[i];
}
int depth=0;
while(depth<5&&!dfs(0,depth))depth++;
if(depth>=5) cout << "5 or more"<<endl;
else cout << depth<<endl;
}
return 0;
}
不过还是有必要提一下,这个估计函数的返回值一定比真实值要小,不是小,而是小于等于.当tot=3时显然是可以等于的. 如果严格小于那么
if(u + f() > depth)return false;//
可以改成if(u + f() >= depth)return false;//
,但是这是错的已修改
注释好评
这么高产?