要素をフリップさせて最大連続要素を最小化する

Question

1と0の配列と数値kが与えられました。最大でk倍（0〜1または1〜0）で配列の要素を反転することができます。

同じ要素を持つ要素の最大連続ブロックのサイズが最小になるように、多くてもK個の要素の状態を反転するアルゴリズムを書く必要があります。

ex: 

Array : 110001111 and k=2; 
Solution is 2 , because: we can change the string to: 110101011, and the length of the maximum consecutive length is minimised to 2. 

Array : 1001 k=1 
Solution is 2, because: If we don't change the input string at all, the answer will be 2. It is the best value we can achieve under the given conditions. 

この問題を解決する方法はありますか？

Answer 1

は私がこの問題を単純化して起動してみましょう： 私たちは、同じ種類のシーケンスを表す、数字のリストを持っている：彼らの合計がn

k操作は、次のいずれかであるされていることを [a1,a2,a3...a_m]は、このような：

1. a_i-1とへ[a_i^1,1,a_i^2]
2. 変更a_iでa_iを交換してください変更a_i
a_{i-1}+1から a_i+1と a_{i-1}へ a_{i-1}-1

にしかし、それはa_i<=2場合は、操作2と3が動作のみ1その後、優れていることをかなり明確だし、一つだけの要素がありますしない限り、総長さは2でありますその場合、何もするのは無意味です。したがって、値を分割する方法の問題であると考えることができます。この場合、の順番は気にしません。

kの操作では、実行する必要がある操作は何ですか。kmax(a1,a2,...)は最後に最小値です

最大文字列の内側にビットを反転しないと、最大値は変更されません。ビットを反転する順番は問題ではないことも明らかです（たとえば、最初にビット番号7を反転してからビット番号4にするか、ビット番号4で開始してからビット番号7を反転するかは関係ありません）。だから、最大の連続ブロックを分割することから始めることもできます。

ブロック最大ブロック数はnであるため、すでにO(n^k)アルゴリズムが見つかりました。

Answer 2

うf(i,len,k,state)はlenが現在のシーケンスの長さ指標i、最大最小の配列を表し、kはこれまでフリップの数であり、stateはa[i]の状態です。その後

：

if a[i] == 0: 
    // starting a new sequence 
    f(i, 1, k, 0) = min(f(i-1, len, k, 1) for all len) 

    // adding to a sequence (len > 1) 
    f(i, len, k, 0) = max(len, f(i-1, len-1, k, 0)) 

    // starting a new sequence 
    f(i, 1, k, 1) = min(f(i-1, len, k-1, 0) for all len) 

    // adding to a sequence (len > 1) 
    f(i, len, k, 1) = max(len, f(i-1, len-1, k-1, 1)) 

if a[i] == 1: 
    ...left as an exercise 

JavaScriptコード：//メタ：[コンセンサスビューをお読みください]（HTTPS、これはフラグを立て得るために探しているユーザーの場合

function f(a,i,len,k,state){ 
 
    // We cannot change the state of a[i] if k is zero 
 
    if (k === 0 && a[i] != state) 
 
    return Infinity; 
 
    
 
    // The first element is a sequence of length 1 
 
    if (i === 0) 
 
    return 1; 
 
    
 
    var oppositeState = state == 0 ? 1 : 0; 
 
    
 
    if (a[i] == state){ 
 
    // Starting a new sequence 
 
    if (len === 1){ 
 
     var best = Infinity; 
 
     
 
     for (var l=1; l<i+1; l++) 
 
     best = Math.min(best, f(a, i-1, l, k, oppositeState)); 
 
    
 
     return best; 
 
     
 
    // Adding to a sequence (len > 1) 
 
    } else { 
 
     return Math.max(len, f(a, i-1, len-1, k, state)); 
 
    } 
 

 
    // a[i] does not equal state 
 
    } else if (k > 0) { 
 
    // Starting a new sequence 
 
    if (len === 1){ 
 
     var best = Infinity; 
 
     
 
     for (var l=1; l<i+1; l++) 
 
     best = Math.min(best, f(a, i-1, l, k-1, oppositeState)); 
 
    
 
     return best; 
 
     
 
    // Adding to a sequence (len > 1) 
 
    } else { 
 
     return Math.max(len, f(a, i-1, len-1, k-1, state)); 
 
    } 
 

 
    // If k is zero, we cannot change the state of a[i] 
 
    } else { 
 
    return Infinity; 
 
    } 
 
} 
 

 
function g(arr,k){ 
 
    var best = Infinity; 
 
    
 
    for (var l=1; l<=2*arr.length; l++) 
 
    best = Math.min(best, f(arr, arr.length-1, Math.ceil(l/2), k, l % 2)); 
 
    
 
    return best; 
 
} 
 

 
console.log(g('110001111',2)); // 2 
 

 
console.log(g('1001',1)); // 2 
 

 
console.log(g('111111',0)); // 6