tc recursive dp 

Problem Statement for BearPlaysDiv2 Problem Statement      Limak is a little bear who loves to play. Today he is playing by moving some stones between three piles of stones. Initially, the piles contain A, B, and C stones, respectively. Limak's goal is to produce three equal piles. Limak will try reaching his goal by performing a sequence of zero or more operations. In each operation he will start by choosing two unequal piles. Let's label their sizes X and Y in such a way that X < Y. He will then double the size of the smaller chosen pile by moving some stones between the two chosen piles. Formally, the new sizes of the two chosen piles will be X+X and Y-X. You are given the ints A, B, and C. Return "possible" (quotes for clarity) if there is a sequence of operations that will make all three piles equal. Otherwise, return "impossible".   Definition      Class: BearPlaysDiv2 Method: equalPiles Parameters: int, int, int Returns: String Method signature: String equalPiles(int A, int B, int C) (be sure your method is public)        Constraints - A, B and C will be between 1 and 500, inclusive.   Examples 0)      10 15 35 Returns: "possible" One valid sequence of operations looks as follows: The initial pile sizes are 10, 15, and 35. For the first operation Limak will choose the piles with 15 and 35 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 30 and 20. After the first operation the pile sizes are 10, 30, and 20. For the second operation Limak will choose the piles with 10 and 30 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 20 and 20. After the second operation each pile has 20 stones, which means that Limak has reached his goal. 1)      1 1 2 Returns: "impossible" No matter what Limak does, there will always be two piles with a single stone each and one pile with 2 stones. 2)      4 6 8 Returns: "impossible" 3)      18 18 18 Returns: "possible" Sometimes Limak can reach his goal without making any operations. 4)      225 500 475 Returns: "possible" This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:         Single Round Match 664 Round 1 - Division II, Level Two

--------------------------------------------------editorial---------------------------------------------------------

in this peoblem dp state is 2 d not 3 d dp[a][b]  since for a given a and b c will always remain same ,

just  memorise whether  a,b,c state has come before or not...

-----------------------------------------------------------code---------------------------------------------

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int dp[5500][5500];

string f="impossible";

int nc=0;

class BearPlaysDiv2

{

int equal(int a,int b,int c)

 {

 

  if(a>=0 && b>=0 && c>=0)

  {

  nc++;

 

  if(dp[a][b]==0)

  {

  if(a==b && b==c) 

        {

     

           f="possible";

   

         }

   

   {

    dp[a][b]=1;

    dp[a][c]=1;

    dp[b][c]=1;

    dp[b][a]=1;

    dp[c][a]=1;

    dp[c][b]=1;

   

     equal(a+a,b-a,c);

   

        equal(a+a,c-a,b);

     equal(b+b,c-b,a);

     equal(b+b,a-b,c);

     equal(c+c,b-c,a);

     equal(c+c,a-c,b);

  }

 }

   

 }

 return 0;

 

 }

string equalPiles(int a, int b, int c) 

 {

 

   equal(a,b,c);

   return f;

 }

};

**Mysterious Present(pick and leave problem with backtracking of path of pick of best answer )

Mysterious Present

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {a1,  a2,  ...,  an}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i  -  1)-th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

Input

The first line contains integers n, w, h (1  ≤ n ≤ 5000, 1 ≤ w,  h  ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers wi and hi — width and height of the i-th envelope (1 ≤ wi,  hi ≤ 106).

Output

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

Sample test(s)

input

2 1 1
2 2
2 2

output

1
1 

input

3 3 3
5 4
12 11
9 8

output

3
1 3 2 

--------------------------------------------------------editorial---------------------------------
 dp[i]= if we pic ith element than no of elements can be picked in future , means no of elements picked after picking ith element

next[i] in the best answer calculation next index which is picked after i th index 

O(N^2) dynamic programming. DP state is index of last chosen envelope, and loop over for the next envelope.

main thing in this problem is that backtracking of best path while calculating maximum chain ,,,,,
this is a very good way to keep track of path of picked elements 
------------------------------------------------------code--------------------------------------------------------------
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int n;
int next[1000000];
int dp[1000000];
vector<pair<int,int> > v;
int solve(int cur)
 {
   
  if(dp[cur]!=-1)
   {
     return dp[cur];
     
  }
  else
  {
   int cur_w=v[cur].first;
   int cur_h=v[cur].second;
   int ret=0;
   int par=cur;
    for(int j=0;j<=n;j++)
    {
       if(v[j].first>cur_w && v[j].second>cur_h)
       {
        int val=solve(j);
         if(val>ret)
          {
           ret=val;
           par=j;
   }
 }
   }
   dp[cur]=ret+1;
   next[cur]=par;
   return dp[cur];
  }
  } 
  
  int main()
   {
   
      cin>>n;
      for(int i=0;i<=n;i++)
       {
        dp[i]=-1;
         int a,b;
          cin>>a>>b;
          v.push_back(make_pair(a,b));
  }
  
 
  int ans=solve(0);
  
   cout<<ans-1<<endl;
   int start=next[0];
   for(int i=0 ;i<ans-1;i++)
    {
     cout<<start<<" ";
     start=next[start];
}
  

   }

------------------------------------------------another editorial-----------------------------------------------------

Mysterious Present

Problem can be solved by dynamic programming approach for O(n2) by time and O(n) by memory.

1. Sort all envelopes by pairs (wi, hi) or by product wi*hi in nondecreasing order. Because of it envelope i can be put in envelope j only ifi < j. That is for any chain {a1, a2, ..., an} is true that a1 < a2 < ... < an.
2. Just delete all envelopes in which card can't be put in.
3. Add to sorted envelopes array a0 - Peter's card.
4. Introduce DP function: dp[i] maximum chain length which ends in i-th envelope.
5. dp[0] = 0, dp[i] = max(dp[j]) + 1, where i ≥ 1, 0 ≤ j < i and j can be put in i. This function can be easily got by previously computed values of it.

Problem answer is max(dp[i]), where 0 ≤ i ≤ n.
For each dp[i] one can remember index p[i] = j with which maximum reached in formula p5. If one knows s - envelope index in which maximal chain ends he can restore all answer sequence (i0 = s, ik+1 = p[ik]).

**Letter (minimum numbers of steps required to conver a string which contan initiall all upper case than lower case letters)

 Letter

Patrick has just finished writing a message to his sweetheart Stacey when he noticed that the message didn't look fancy. Patrick was nervous while writing the message, so some of the letters there were lowercase and some of them were uppercase.

Patrick believes that a message is fancy if any uppercase letter stands to the left of any lowercase one. In other words, this rule describes the strings where first go zero or more uppercase letters, and then — zero or more lowercase letters.

To make the message fancy, Patrick can erase some letter and add the same letter in the same place in the opposite case (that is, he can replace an uppercase letter with the lowercase one and vice versa). Patrick got interested in the following question: what minimum number of actions do we need to make a message fancy? Changing a letter's case in the message counts as one action. Patrick cannot perform any other actions.

Input

The only line of the input contains a non-empty string consisting of uppercase and lowercase letters. The string's length does not exceed105.

Output

Print a single number — the least number of actions needed to make the message fancy.

Sample test(s)

input

PRuvetSTAaYA

output

5

input

OYPROSTIYAOPECHATALSYAPRIVETSTASYA

output

0

input

helloworld

output

0

---------------------------------------------editorial-------------------------------------------------------

#include<iostream>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
  char arr[1000001];
  int fdp[10000001];
  int bdp[10000001];
 
int main()
 {
    //freopen("abc.txt","r",stdin);
    int n;
     //cin>>n;
      cin>>(arr+1);
      // cout<<(arr+1)<<endl;
      int len=strlen(arr+1);
       for(int i=1;i<=len;i++)
        {
            if(arr[i]>='a' && arr[i]<='z') fdp[i]=fdp[i-1]+1;
            else fdp[i]=fdp[i-1];
        }
        for(int i=len;i>=0;i--)
        {
            if(arr[i]>='A' && arr[i]<='Z') bdp[i]=bdp[i+1]+1;
            else bdp[i]=bdp[i+1];
        }
        int ans=INT_MAX;
       /*  for(int i=1;i<=len;i++) cout<<fdp[i]<<" ";
         cout<<endl;
          for(int i=1;i<=len;i++) cout<<bdp[i]<<" ";
          cout<<endl;*/
          for(int i=0;i<=len;i++)
           {
            ans=min(ans,fdp[i]+bdp[i+1]);
           }
            cout<<ans<<endl;
            return 0;
 }