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

Автор I_love_Saundarya, история, 6 лет назад, По-английски

Problem-link : — https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/shift-the-array-4074fac2/

You are given a string that contains lowercase English letters. In one step, you can choose a character and assign the next letter in the alphabet to it. (a-->b,b-->c,etc..and yea,z--->a). The number of indices where a[i]!=a[i+1] is given as f(string).

You are given a number 'k'.Now, your task is to determine the minimum number of steps required to perform on the string to obtain a string such that f(new-string)<=k.

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

you can use dp(pos, current_letter, misses). current_letter forces than a[pos] = current_letter + 'a' (0 <= current_letter < 26)

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

(del)

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

(del)

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

This problem is very similar to https://codeforces.net/contest/1108/problem/D .