OJ Board

Code: Select all

count[0]=1
for(i=0;i<v.size();i++)
{
  for(j=0;j<i;j++)
          if(v[j]*5 <= v[i]*4)
              best[i]=max(best[i],best[j]+1);

 if(best[i]>1)
   for(j=0;j<i;j++)
         if(best[i]==best[j]+1)
             count[i]+=count[j];
else 
  count[i]=1;

In the end sum of all the count[x] where best[x] is the maximum

}

Code: Select all

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<cctype>
#include<cstring>
#include<cstdlib>
using namespace std;

int
main ()
{
  int no;
  string s;
  getline (cin, s);
  sscanf (s.c_str (), " %d", &no);

  while (no--)
    {
      int i;
      getline (cin, s);
      vector < int >v;
      int arr[30];
      memset (arr, 0, sizeof (arr));

      for (i = 0; i < s.size (); i++)
	if (isupper (s[i]))
	  {
	    if (!arr[s[i] - 'A' + 1])
	      {
		arr[s[i] - 'A' + 1] = 1;
		v.push_back (s[i] - 'A' + 1);
	      }
	  }


      sort (v.begin (), v.end ());
	if(v.size()==1){ printf("1 1\n"); continue; }
	if(v.size()==0){ printf("0 0\n"); continue; }
/*		for(i=0;i<v.size();i++)
			printf("%c,",v[i]+'A'-1);
		printf("\n");
*/

      int best[v.size () + 1], j;
      unsigned long long cnta[v.size () + 1];
      memset (best, 0, sizeof (best));
      memset (cnta, 0, sizeof (cnta));


      cnta[0] = 1;
      for (i = 0; i < v.size (); i++)
	{
	  if (best[i] == 0)
	    {
	      best[i] = 1;
	    }
	  for (j = 0; j < i; j++)
	    {
	      if (v[j] * 5 <= 4 * v[i])
		{
		  if ((best[j] + 1) >= best[i])
		    {
		      best[i] = best[j] + 1;
		    }
		}
	    }
	  if (best[i] > 1)
	    {
	      for (j = 0; j < i; j++)
		{
		  if (best[i] == (best[j] + 1))
		    cnta[i] += cnta[j];
		}
	    }
	  else
	    cnta[i] = 1;
	}
/*
		for(i=0;i<v.size();i++)
			printf("%d,",best[i]);
		printf("\n");
*/
      int mmax = 1;
      for (i = 0; i < v.size (); i++)
	mmax = max (mmax, best[i]);
      unsigned long long cnt = 0;
      for (i = 0; i < v.size (); i++)
	if (best[i] == mmax)
	  cnt += cnta[i];
      printf ("%d %llu\n", mmax, cnt);

    }
  return 0;
}

Code: Select all

Removed

Code: Select all

rec( i, len ) // This will find the number strings that have length 'len' and the first character assigned in the string is at least the ith character from string a[].
{
    res = rec( i + 1, len ); // Find the result from the next character
    find j from i + 1 to end, where a[j] can be placed after a[i]
    res += rec( j, len - 1 ); // Since we have placed i and a[j] can be placed after a[i], so, a[j+1], a[j+2], ... can also be placed after a[i]
    return res;
}