Wonderful DP problem
Разница между en6 и en7, 20 символ(ов) изменены
Given a sequence of integers ,find a subsequence of largest length such that in the subsequence adjacent elements are not equal at most k times. n<=1e3,k<=n<=1e3 .. Any Hints or ideas?↵

*upd*: Thank You everyone.↵
Final solution:↵

suppose u are at index i.say p denotes index of prev elements.say given array is a ;↵
dp[x][y]=max length when u have explored only till x index and atmost y non equla adjacent pairs.↵

brute force dp(O(n3)):-↵
for(int p=0;p<i;p++)↵
{ for(int j=0;j<k;j++)↵
  {int a=-1,b=-1;↵
  if(a[i]==a[p]) a=dp[p][j]+1;↵
  else if(j>=1) b=dp[p][j-1]+1;↵

  dp[i][j]=max{dp[i][j],a,b}↵
}↵

}↵

Very easy to optimise:↵
 we want just max out of dp[0 ....... i-1][j]   and max out of dp[0...... i-1][j-1]
 using map[value][j].I have tried to be accurate .Still U find some thing to be correct pls inform.↵
 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский FO7 2023-08-12 14:21:46 20 Tiny change: ' i-1][j-1].I have t' -> ' i-1][j-1] using map[value][j].I have t'
en6 Английский FO7 2023-08-12 14:18:00 94
en5 Английский FO7 2023-08-12 14:14:12 10
en4 Английский FO7 2023-08-12 14:13:16 708
en3 Английский FO7 2023-08-11 09:16:21 13 Tiny change: 's or ideas to optimise ?' -> 's or ideas?'
en2 Английский FO7 2023-08-11 09:09:12 32 Tiny change: 'n<=1e3 .. ' -> 'n<=1e3 .. Any Hints or ideas to optimise ?'
en1 Английский FO7 2023-08-10 23:05:45 185 Initial revision (published)