#include<bits/stdc++.h>
using namespace std;
int ar[105] = {0};
int dp[105][105][105];
 
int max_paint(int idx , int idb , int idw)
{
  if(idx == 1)
    {
      if(ar[idx] > ar[idw] || ar[idx] < ar[idb] )return 1;
      return 0;
    }
  if(dp[idx][idb][idw] != -1)return dp[idx][idb][idw];
  int f1 = 0 , f2 = 0 ;
 
  if(idb == 0 || idw == 0 || ar[idx] > ar[idw] || ar[idx] < ar[idb] )
  {
    if( idb == 0 || ar[idx] < ar[idb])   
      f1 = 1 + max_paint(idx-1 , idx , idw);
    if(idw == 0 || ar[idx] > ar[idw])
      f2 = 1+ max_paint(idx-1 , idb ,idx );
    dp[idx][idb][idw] = max(f1 , max( f2 , max_paint(idx-1 , idb , idw ) ) );
  }
  else

#include<bits/stdc++.h>
using namespace std;
int dp[3][5010] = {0};
 
int main(int argc , char **argv)
{
  int len;string s;
  cin >> len >> s;
  for(int l = 2 ; l <= len ; l++)
    {
      for(int i = 0 ; i < (len-l+1) ; i++ )
	{
	  int j = (i+l-1);
	  if(s[i] == s[j])
	    dp[l%3][j] = dp[(l-2) % 3][j-1];
	  else
	    dp[l%3][j] = 1+min(dp[(l-1)%3][j] ,dp[(l-1)%3][j-1]);
	}
    }
  cout << dp[len%3][len-1]<<"\n";
  return 0;
}

Hussain , i did come up with an idea to solve this problem( MSTQueries ).But due to some unknown error it is giving me TLE . I read the editorial of the problem too which i completely understood.But since my approach was different i decided to give it a try.

Following is my solution:

1. I find the MST only once and store this MST in an adjacency list.
2. Now , for query 1 i.e changing the weght of a given edge "e" to zero.Since this edge shoukd be a part of MST , therefore , including it will create a cycle . I then do a DFS on the MST (which now includes a cycle) to detect the cycle and on my way back from DFS recursion i get the maximal edge "e2" that will be replaced by the "e".
3. Since "e2" will always be part of the cycle created by "e" , we are sure that now the new MST will have no cycle.

The above approach only handles the case when query ...

#include<bits/stdc++.h>
using namespace std;
 
int grid[305][305][305][2];
int o_g[301][301];
 
int main(int argc , char ** argv)
{
  int r , c , d;
  cin >> r >> c >> d;
  int sum_rt , sum_dn; 
  memset(grid , 0 , sizeof(grid));
  for(int i = 1 ; i <= r ; i++)
    {
      for(int j =1 ; j <= c ; j++)
	cin >> o_g[i][j];      
    }
 
  grid[1][1][d+1][0] = 1;
  grid[1][1][d+1][1] = 0;
  for(int i = 2 ; i <= c ; i++)
	{
	  if(!o_g[1][i])break;
	  if(i - 1 <= d)

Ashish , thanx a lot for helping me out. But this is the exact thing that was confusing me yesterday. If min_ar[1] can't be selected , how is it that it rules out the possibility of selecting ar[1]. For a case where ar[1] is less than ar[n] and min_ar[1] is not selected. How is it that always including ar[n] in the path works?

Keshav , could you please take a look at my code . I am getting WA for three test cases. I can't seem to figure out why.I first store the minimums along with the paths.If the second position is more suitable to start .Then i use the paths to go to the last position. Finally i check if i can include the last position or the first one. Please help!!

#include<bits/stdc++.h>
using namespace std;
int main(int argc , char **argv)
{
 
  int n , sum1 = 0,sum2 = 0 ;
  cin >> n;
  int ar[n+1] , min_ar[n+1],path[n+1] ;
  for(int i = 1 ; i <= n ; i++)
    {cin >> ar[i];}
  if(n == 1){cout << ar[1] ;return 0 ;}
 
  if(n == 2){cout << min(ar[1 ] , ar[2]);return 0;}
 
  min_ar[n] = ar[n];min_ar[n-1] = ar[n-1];
 

Spent an entire day solving this problem. Following is my solution. I would appreciate if i get a feedback on what is it that i need to improve.

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int len , start , sum1 =0 ;
  cin >> len >> start;
  int  ar[len+1];ar[0] = 0;
  for( int i = 1 ; i<= len ; i++)
    {cin >>  ar[i];}
  vector<int> jmp1(len+1) ;jmp1[0] = 0;
  vector<int> jmp2(len+1) ; jmp2[0] = 0;
  jmp1[1] = ar[1];
  jmp1[2] = ar[2]+ar[1];
  for(int j = 1 ; j <= len ;j++)
    {if(j==1)jmp1[j] = ar[j];
      else if(j==2)jmp1[j] = ar[j]+ar[1];
      else jmp1[j] = ar[j]+max(jmp1[j -1],jmp1[j-2]);
    }
 

Ashish, do you have any more resources(apart from the one you shard earlier) which explain solving DP problems using their implicit DAGs. That would be a great help.

Following is my solution for the problem using bottom-up approach....any suggestions are welcome...

#include<bits/stdc++.h>
using namespace std;
int main()  
{
 
  int days;
  cin >> days;
  int day_array[days+1] , time_array[days+1] , min_array[days+1];
  time_array[0] = 0;
  for(int i = 1 ; i <= days ; i++)
    { cin >> day_array[i];time_array[i] = 0; min_array[i] = 0;}
  min_array[days] = day_array[days];  min_array[days - 1] = day_array[days - 1];
  min_array[days-2] = day_array[days - 2];
  for(int i = (days - 3) ; i>= 1 ;i--)
    min_array[i] = day_array[i]+min(min_array[i+1] , min(min_array[i+2],min_array[i+3]));
  cout << min(min_array[1] , min(min_array[2],min_array[3]));
  return 0;
}

I was able to solve this problem using the hints given by Mohit. However, i would really want to understand your approach for this problem. Could you explain your algo using an example ?That would help .