Перевернутый массив ядер и нулей

Question

У меня есть массив A состоит из массива ones и zeroes. За одну операцию я могу выбрать Range 1 to i1<=i<=N и flip массив и invert.
Мне нужно было найти минимальную операцию, необходимую для этого.
Для Ex:

A = 0010 

В первой операции в диапазоне от 1 до 4 Сначала мы переворачивать массив и инвертировать его

A = 1011 

Во второй операции в диапазоне от 1 до 1 Сначала мы перевернуть массив и инвертировать это

A = 0011 

в thrid эксплуатацию в диапазоне от 1 до 2 сначала мы перевернуть массив и инвертировать его

A = 1111 

Необходимо выполнить три операции. Как я могу найти Minumum количество операций

My Approach: 

сделать последний элемент, как один и продолжить

while(end>=0){ 

    if(A[end]==1){ end--;continue;} 

    int i=0; 

    if(A[0]==1) { 
    ans++; 
    A[0]=0; 
    } 
    i = 0; 
    int j = end; 

    while(j>=i){ 
     // Flip the Array and inverted it. 
    } 
    ans++; 
    end--; 

} 

Это жадный подход и я думаю, что это не будет работать.

Answer 1

Трудно сказать, является ли это оптимальное решение (хотя это выглядит, как это) Я хотел бы сделать это так (C++):

int puzzle_flip_invert(int *a,int n) 
    { 
    int i1,m,N=n,i,j; char b; 
    // here print the input a[N] 

    // solve the puzzle 
    for (m=0;;m++) 
     { 
     // starting ones -> zeros 
     if (a[0]==1) 
      { 
      for (i1=0;(i1<n-1)&&(a[i1+1]==1);i1++); 
      if (i1==n-1) break; // solution found 
      } 
     // cut ending ones and then ending zeros -> ones 
     else for (i1=n-1;(i1>=0)&&(a[i1]==1);i1--,n--); 
     // flip and invert a[i] i=<0,i1> 
     for (i=0,j=i1;i<=j;i++,j--) 
      { 
      b=1-a[i]; a[i]=1-a[j]; a[j]=b; 
      } 
     // here print partial solution a[N] and used range <1,i1+1> 
     } 
    // here print the result m 
    return m; 
    } 

использование:

int a[4]={0,0,1,0}; 
puzzle_flip_invert(a,4); 

выход (извините не включал код печати, поскольку он зависит от платформы):

0010 
1011 range: <1,4> 
0011 range: <1,1> 
1111 range: <1,2> 
-------------- 
Needed: 3 steps. 
-------------- 

[ 0.013 ms] 

Основная идея (частично основана на предложении Павла Хэнкин в) заключается в следующем:

1. если массив начинается с тех

   затем проверить, сколько их там вместе. Если вся строка останавливается, вы нашли решение, если не переверните их и не инвертируйте, чтобы строка начиналась с нулей. Это важно, поэтому мы можем избавиться от конечных нулей позже.

2. если массив начинается с нулей

   затем проверить, сколько из них в конце и сократить размер массива n ими в этой части массива уже сделано. затем переверните и инвертируйте остальные. Это будет преобразовывать столько же последних нулей из вырезанной части, сколько возможно.

3. Гото # 1

[Примечания]

Как я уже говорил, я не знаю, если этот подход является оптимальным решением. Для этого вам нужно будет сделать какое-то доказательство, которое не является моей чашкой чая, поэтому я бы даже не попробовал. Во всяком случае, я думаю, что это хорошая стартовая точка ...

Остерегайтесь array индексирование в C++ от 0 не от 1 !!! Отпечатки увеличиваются, поэтому диапазоны соответствуют вашему результату.

Еще несколько примеров:

010 
101 range: <1,3> 
001 range: <1,1> 
111 range: <1,2> 
-------------- 
Needed: 3 steps. 
-------------- 

00001111001101110 
10001001100001111 range: <1,17> 
00001001100001111 range: <1,1> 
11110011011111111 range: <1,13> 
00000011011111111 range: <1,4> 
10011111111111111 range: <1,9> 
00011111111111111 range: <1,1> 
11111111111111111 range: <1,3> 
-------------- 
Needed: 7 steps. 
--------------