Блог пользователя shakil_AUST

Автор shakil_AUST, 9 лет назад, По-английски

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Solved the problem after seeing this post.

lets take dp[flip_allowed][flipped][i][j][k]=minimum number of flip needed to match x[i....j] with Y[k ..... k+j-i], 'filp_allowed' and 'flipped' are boolean values that denotes whether we are allowed to flip the current segment X[i....j] and whether the portion x[i....j] is flipped respectively. now to match x[....] to y[...], we can either flip the entire segment x[....] , or we will at least leave one character from any end of x[i....j] if that matches Y[k ........ k+j-i].

So the state transitions will look like this

if(flip_allowed) dp[filp_allowed][flipped][i][j][k] = 1 + dp[0][!flipped][i][j][k];
if(!flipped) 
{
   if(X[i]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][0][i+1][j][k+1];
   if(X[j]==Y[k+j-i]) dp[flop_allowed][flipped][i][j][k]=dp[1][0][i][j-1][k];
}

else if(flipped)
{
   if(X[j]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i][j-1][k+1];
   if(X[i]==Y[k+j-i]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i+1][j][k];
}

Hope that helps.