//1.3_pancake_2.cpp   by  flyinghearts#qq.com
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;

class Pancake{
 public:
  Pancake(int size=0):max_size(0) { init(size); }
  void init(int size=0);
  void print() const;
  void process();               //显示最优解的翻转过程
  int run(const int cake_arr[], int size, bool show=true);
  
 private: 
  vector<int> cake;            //当前各个烙饼的状态
  vector<int> cake_swap;       //每次翻转的烙饼位置
  vector<int> result;          //最优解中，每次翻转的烙饼位置
  vector<int> cake_order;      //第step+1次翻转时，翻转位置的优先顺序
  int max_size;                //预分配数组大小
  int min_swap;                //最优解的翻转次数
  int min_swap_init;           //最优解的翻转次数初始值
  int count_search;            //search_cake被调用次数
  int count_reverse;           //reverse_cake被调用次数
  int cake_size;               //要处理的烙饼数组大小
  const int *cake_old;         //要处理的原烙饼数组

  void search_cake(int size, int step, int least_swap_old);
  void reverse_cake(int index); //翻转0到index间的烙饼
  Pancake(const Pancake&);
  Pancake& operator=(const Pancake&);
};


void Pancake::init(int size)
{
  if (size<=0) size=16;
  if (size>max_size){
    max_size=size;
    cake.resize(size);
    cake_swap.resize(size*2);
    result.resize(size*2);
    cake_order.resize(size*size*2);
  }
  min_swap=0;
  min_swap_init=0;
  count_search=0;
  count_reverse=0;
  cake_size=0;
  cake_old=NULL;
}

void Pancake::print() const
{
  if (min_swap>0){
    cout<< "minimal_swap initial: "<< min_swap_init<< "  final: "<< min_swap
        << "\nsearch/reverse function was called: "<< count_search
        << "/"<< count_reverse<< " times\nsolution: ";
    for (int i=0;i<min_swap; ++i) cout<< result[i]<< " ";
    cout<< "\n\n";
  }
}

void Pancake::process()
{
  if (min_swap>0 && cake_size>0 && cake_old != NULL){
    cake.assign(cake_old, cake_old+cake_size);
    int i,j;
    const int WIDTH=3;
    cout<< setw(2*WIDTH+3)<< "No. ";
    for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< j<<" ";
    cout<<"\n";    
    cout<< setw(2*WIDTH+3)<< "old: ";
    for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";
    cout<<"\n";
    for (i=0; i<min_swap; ++i){
      reverse_cake(result[i]);
      cout<< setw(WIDTH)<< i+1<< "-"<< setw(WIDTH)<< result[i]<<": ";
      for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";
      cout<<"\n";
    }
    cout<<"\n\n";
  }
}

void Pancake::reverse_cake(int index)
{
   ++count_reverse;
   int *beg=&cake[0], *end=&cake[0]+index;
   int tmp;
   while(beg<end){
     tmp = *beg;
     *beg++ = *end;
     *end-- = tmp;
   }
}

int Pancake::run(const int cake_arr[], int size, bool show)
{
  count_search=0;
  count_reverse=0;
  min_swap=0;
  cake_size=0;
  cake_old=NULL;
  if (cake_arr==NULL || size<=1) return 0;
  while (size>1 && size-1==cake_arr[size-1]) --size; //去除末尾已就位的烙饼
  if (size<=1) return 0;

  if (size>max_size) init(size+16);
  cake.assign(cake_arr,cake_arr+size);
  cake_size=size;
  cake_old=cake_arr;

  int i, least_swap=0, sz=size-1, *p=&result[0];
  while (sz>0){  //先计算一个可能解
    for (i=0; i<=sz; ++i)
      if (cake[i]==sz) break;
    if (i!=0){
      reverse_cake(i);
      *p++=i;         //result.push_back(i);
      ++min_swap;
    }
    reverse_cake(sz);
    *p++=sz--;         //result.push_back(sz);
    ++min_swap;
    while(sz>0 && sz==cake[sz]) --sz;
  }

  cake.assign(cake_arr,cake_arr+size);     //恢复原来的数组
  cake.push_back(size);              //多放一个烙饼，避免后面的边界判断
  cake_swap[0]=0;                    //为方便起见，假设第0步翻转的烙饼编号为0
  for (i=0,least_swap=0; i<size; ++i)
    if (cake[i]-cake[i+1]+1u >2) least_swap++;
    //等同于if (cake[i]-cake[i+1]>1 || cake[i]-cake[i+1]<-1) least_swap++;
  min_swap_init=min_swap;
  if (least_swap != min_swap)
     search_cake(size,0,least_swap);
  if (show) print();
  return min_swap;
}

void Pancake::search_cake(int size, int step, int least_swap_old)
{
  ++count_search;
  while (size>1 && size-1==cake[size-1]) --size;  //去除末尾已就位的烙饼

  int *first=&cake_order[0]+step*cake_size;
  int *last=first+size, *low=first, *high=last, *p=first;
  int least_swap=least_swap_old;

  for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){
    if (pos==last_swap) continue;
    least_swap = least_swap_old ;
    if (cake[pos]-cake[pos+1]+1u<=2) ++least_swap;
    if (cake[0]-cake[pos+1]+1u<=2) --least_swap;

    if (least_swap+step >= min_swap) continue;
    if (least_swap == 0){
      cake_swap[step]=pos;
      result.assign(&cake_swap[1],&cake_swap[1]+step+1);
      min_swap= step;
      return;
    }

    if (least_swap==least_swap_old) *low++ =pos;
    else if (least_swap>least_swap_old) *--high =pos;
    else{ //先处理使least_swap_old减小1的翻转
      cake_swap[step] = pos;
      reverse_cake(pos);
      search_cake(size,step,least_swap);
      reverse_cake(pos);
    }
  }

  //再处理使least_swap_old不变的翻转
  for(least_swap=least_swap_old,p=first; p<low; p++){
    if (least_swap+step >= min_swap) return;
    cake_swap[step] = *p;
    reverse_cake(*p);
    search_cake(size,step,least_swap);
    reverse_cake(*p);
  }

  //最后处理使least_swap_old增加1的翻转
  for(++least_swap, p=high; p<last; p++){
    if (least_swap+step >= min_swap) return;
    cake_swap[step] = *p;
    reverse_cake(*p);
    search_cake(size,step,least_swap);
    reverse_cake(*p);
  }

}

int main()
{
  int aa[10]={3,2,1,6,5,4,9,8,7,0};
  Pancake cake(16);
  cake.run(aa,10);
  cake.process();

 //遍历求第n个烙饼数
  const int N=8;
  int i,j,max=0,tmp;
  int arr[N];
  for (j=1;j<=N;++j){
    for (i=0; i<j; ++i) arr[i]=i;
    max=0;
    while(next_permutation(arr,arr+j)){
      tmp=cake.run(arr,j,0);
      if (tmp>max) max=tmp;
    }
    cout<<j<<" "<<max<<endl;
  }
}

