[关闭]
@zzzc18 2018-01-18T12:33:43.000000Z 字数 1413 阅读 480

[IDA*]序列(sequence)

TEST 搜索


序列(sequence)

【题目描述】
给定一个1~n的排列x,每次你可以将x1~xi翻转。你需要求出将序列变为
升序的最小操作次数。有多组数据。
【输入数据】
第一行一个整数t表示数据组数。
每组数据第一行一个整数n,第二行n个整数x1~xn。
【输出数据】
每组数据输出一行一个整数表示答案。
【样例输入】

1
8
6 1 3 2 4 5 7

【样例输出】

7

【数据范围】
对于100%的测试数据,t=5,n<=25。
对于测试点1,2,n=5。
对于测试点3,4,n=6。
对于测试点5,6,n=7。
对于测试点7,8,9,n=8。
对于测试点10,n=9。
对于测试点11,n=10。
对于测试点i(12<=i<=21),n=i。
对于测试点22,23,n=22。
对于测试点24,25,n=23。

Solution

考试的时候已经猜到是 IDA* 了,可是一直没想出来估价函数是啥,写了个迭代加深搜索骗了个暴力分。。。

考虑到这是一个排列,最终的状态一定是 num[i]+1==num[i+1]
而每次交换最多只会改变一组相邻元素的差值
所以对于某一个状态,相邻的元素之差大于 的个数就可以作为估价函数的值,因为最优解步数不小于这个。

  1. #include<ctime>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. const int MAXN = 36;
  8. int n;
  9. int tmp[MAXN];
  10. int num[MAXN];
  11. int ans;
  12. bool check(){
  13. for(int i=1;i<n;i++)
  14. if(num[i]+1!=num[i+1])
  15. return false;
  16. return true;
  17. }
  18. void SWAP(int l,int r){
  19. for(int i=l;i<=r;i++)
  20. tmp[i]=num[i];
  21. for(int i=r,j=l;i>=l;i--,j++)
  22. num[i]=tmp[j];
  23. }
  24. bool H(int x,int limit){
  25. int re=0;
  26. for(int i=1;i<n;i++){
  27. if(abs(num[i]-num[i+1])>1)
  28. re++;
  29. }
  30. return re+x<=limit;
  31. }
  32. void DFS(int x,int limit){
  33. if(x==limit+1){
  34. if(check())
  35. ans=limit;
  36. return;
  37. }
  38. for(int i=1;i<=n;i++){
  39. if(ans!=2*n+1)
  40. return;
  41. SWAP(1,i);
  42. if(H(x,limit))
  43. DFS(x+1,limit);
  44. SWAP(1,i);
  45. }
  46. }
  47. void solve(){
  48. ans=2*n+1;
  49. if(check()){
  50. puts("0");
  51. return;
  52. }
  53. for(int i=1;i<=2*n;i++){
  54. DFS(1,i);
  55. if(ans!=2*n+1)
  56. break;
  57. }
  58. printf("%d\n",ans);
  59. }
  60. int main(){
  61. freopen("sequence.in","r",stdin);
  62. freopen("sequence.out","w",stdout);
  63. int kase;
  64. scanf("%d",&kase);
  65. while(kase--){
  66. scanf("%d",&n);
  67. for(int i=1;i<=n;i++)
  68. scanf("%d",&num[i]);
  69. solve();
  70. }
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注