OJ Board

Code: Select all

int main()
{
	int n;
	cin>>n;
	string s;
	getline(cin,s);
	for(int kase=0;kase<n;kase++)
	{
		vector<int> x;
		if(kase>0)
			cout<<endl;
		else
			getline(cin,s);
		while(getline(cin,s))
		{
			if(s.length()==0)
				break;
			const char *cs=s.c_str();	
			x.push_back(atoi(cs));
		}
		vector<int> y=lis(x),z;
		cout<<"Max hits: "<<y.size()<<endl;
		for(int i=0;i<y.size();i++)
			cout<<x[y[i]]<<endl;
	}
	return 0;
}	

Code: Select all

//  Q497: Strategic Defense Initiative
//  LIS(最長遞增子序列) 
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <ctype.h>

using namespace std;

int main()
{
    int n = 0;
    vector<int> array, array2;
    char str[11];
    
    cin >> n;
    getchar();
    cin.getline(str, 11, '\n');
    
    for(n--; n >= 0; n--)
    {
        array.clear();
        array2.clear();
        
        while(cin.getline(str, 11, '\n'))
        {
            if(strlen(str) == 0)
                break;
            
            array.push_back(atoi(str));
        }
        
        for(int i = 0; i < array.size(); i++)
        {
            if(array2.size() == 0)
                array2.push_back(array[i]);
            else
            {
                if(array2[array2.size()-1] < array[i])
                    array2.push_back(array[i]);
                else if(array2.size() == 1)
                    array2[0] = array[i];
                else if(array2[array2.size()-2] < array[i])
                    array2[array2.size()-1] = array[i];
            }
        }
        
        cout << "Max hits: " << array2.size() << endl;
        
        for(int i = 0; i < array2.size(); i++)
            cout << array2[i] << endl;
        
        if(n != 0)
            cout << endl;
    }
    
    return 0;
}

Code: Select all

#include <cstdio>
#include <string>
#include <algorithm>
#define INF 1<<29
#define MAX 100000

using namespace std;

int A[MAX];
int L[MAX];
int P[MAX];

int maxLenth(int array[], int n){
	int max = -INF,i;
	for(i = 0; i<n; i++)
		if(array[i] > max)
			max = i;
		return max;
}

void printPath(int P[],int p){
	if(p == INF)
		return;
	printPath(P,P[p]);
	printf("%d\n",A[p]);
}

void setInitial(int n){
	for(int i = 0; i<n; i++){
		P[i] = INF;
		L[i] = 1;
	}
}


int main(){
	//freopen("in.txt","rt",stdin);
	int input,i,j,max,n;
	char str[20];	
	scanf("%d\n",&input);	
	while(input--){		
		i = 0;
		while(gets(str) && strcmp(str,"")){
			sscanf(str,"%d",&A[i++]);
		}		
		n = i;
		setInitial(n);
		for(i = 0; i<n; i++){
			for(j = i+1; j<n; j++){
				if(A[i] < A[j] && L[j] < L[i]+1)
				{
					L[j] = L[i] + 1;
					P[j] = i;
				}
			}
		}		
		max = maxLenth(L,n);
		printf("Max hits: %d\n",L[max]);
		printPath(P,max);
		printf("\n");
	}
	
	return 0;
}

Code: Select all

    void printPath(int P[],int p){
       // Two array-varialble in the same name P[], (one global, another local)

       if(p == INF)
          return;
       printPath(P,P[p]);
       printf("%d\n",A[p]);
    }

Code: Select all

    int maxLenth(int array[], int n){
       int max = -INF,i;
       for(i = 0; i<n; i++)
          if(array[i] > max)
             max = i;
       return max;
    }

Code: Select all

	gets(str);
		while(str[0]!=NULL)
		{
			array[i++]=atoi(str);
			gets(str);		
		}
	

Code: Select all

      while(str[0]!=NULL)
      {
         array[i++]=atoi(str);
         gets(str);      
      }

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>

using namespace std;

int n,t;
char IN[10];
int s[100];
int dp[100];
int parent[100];
int anw;
void print(int x)
{
     if(parent[x]!=-1)print(parent[x]);
     cout<<s[x]<<endl;
}

main()
{
     while(cin>>t)
     {
          cin.getline(IN,10);
          cin.getline(IN,10);
          while(t--)
          {    
               n=-1;
               while(cin.getline(IN,10))
               {
                    if(strlen(IN)==0)break;
                    n++;
                    s[n]=atoi(IN);
               }
               n++;
               for(int i=0;i<n;i++)dp[i]=1,parent[i]=-1;
               for(int i=0;i<n;i++)
                    for(int j=i+1;j<n;j++)
                         if(s[j]>s[i])
                              if(dp[i]+1>dp[j])
                              {
                                   dp[j]=dp[i]+1;
                                   parent[j]=i;
                              }
               anw=0;
               for(int i=0;i<n;i++)
                    anw=max(anw,dp[i]);
               cout<<"Max hits: "<<anw<<endl;
               for(int i=n-1;i>=0;i--)
                    if(dp[i]==anw)
                    {
                         print(parent[i]);
                         cout<<s[i]<<endl;    
                    }
          }   
     }

}

Code: Select all

/*497*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

int main () 
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int amm;
    scanf("%d",&amm);
    char ss[100];
    gets(ss);
    gets(ss);
    while (amm--)
    {
          int s[10000];
          int g[10000];
          int i=0;
          while (1)
          {
                if(gets(ss)==NULL) break;
                if(!strlen(ss)) break;
                s[i++]=atoi(ss);                
          }
          int str[10000];
          int val[10000];int p=1;
          int ans=1;
          str[0]=s[0];
          val[0]=p;   
          for (int j=1;j<i;j++)
          {
              //strengthen
              if (s[j]>str[ans-1])
              {
                 str[ans]=s[j];
                 val[ans]=p++;
                 ans++; 
                 for (int l=ans-1;(l==ans-1||val[l+1]>val[l])&&l>=0;l--)
                 {
                     g[l]=str[l];
                     //printf("%d ",g[l]);
                 }
                 //puts("");
                 continue;                
              }
              
              int pt=lower_bound(str,str+ans,s[j])-str;
              val[pt]=p++;
              str[pt]=s[j];
              //printf("xx\n");
          }   
          printf("Max hits: %d\n",ans);
          for (int p=0;p<ans;p++)
              printf("%d\n",g[p]);
          if (amm)puts("");    
    }
    return 0;
}