OJ Board

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main(int argc, char**argv) {


    int cnt=0;
    int number;
    
    while(1)
    {
        if(cnt!=0)cout<<endl;

        scanf("%d",&number);
        
        if(number==-1)goto end;

        
    cnt++;
    vector<int> input;
    input.push_back(number);
    
    while(scanf("%d",&number)==1)
    {
        if(number==-1)break;
        input.push_back(number);
    }

    int n=input.size();
    int dp[n];
    int maximum=0;
    for(int i=0;i<input.size();i++)
    {
        dp[i]=1;

        for(int j=0;j<i;j++)
            if(input[i]<=input[j])dp[i]=max(dp[i],dp[j]+1);

        maximum=max(dp[i],maximum);
    }

    cout<<"Test #"<<cnt<<':'<<endl;
    cout<<"  maximum possible interceptions: "<<maximum;

    }

 
    end:
    return 0;
}

Code: Select all

#include<stdio.h>

long height[10000], length[10000];

int main()
{
	long i, j, count, n, max;
    
	count=0;
	while(1)
	{
		scanf("%ld", &height[0]);

		length[0]=1;
		if(height[0]<0)
			break;

		n=1;
		while(scanf("%ld", &height[n])==1)
		{
			if(height[n]<0)
				break;

			length[n]=1;			
			for(j = n-1; j>=0; j--)
			{
				if(height[n] <= height[j] && (length[j] + 1) > length[n])
				{ 
					length[n]= 1+length[j]; 
				}
			}
			n++;
		}

		max=1;
		for(i=0; i<=n; i++)
		{
			if(max<length[i])
				max=length[i];
		}
		

		printf("Test #%ld:\n",++count);
		printf("  maximum possible interceptions: %ld\n\n",max);

		for(i=0; i<=n; i++)
			length[i]=height[i]=0;
	}
			
	return 0;
}

Code: Select all

#include<stdio.h>
int data[40000];
int main(){
	int cases=1;
	while(1){
		int n=0;
		while(scanf("%d",&data[n++])==1){
			if(data[n-1]==-1)break;
		}
		if(data[0]==-1)break;
		n--;
		int length[n],maxlen=1;
		for(int i=0;i<n;i++)
			length[i]=1;
		for(int i=0;i<n-1;i++){
			for(int j=i+1;j<n;j++){
				if(data[j]<=data[i]&&length[i]+1>length[j])
					length[j]=length[i]+1;
				if(length[j]>maxlen)
					maxlen=length[j];
			}
		}
		printf("Test #%d:\n",1);
		printf("  maximum possible interceptions: %d",maxlen);
		puts("\n");
	}
	return 0;
}

Code: Select all

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;

#define MAX 10000

long c[MAX][MAX], N;
long sorted[MAX], unsort[MAX];

long LCS_LENGTH()
{
	long i, j;

	for(i=0; i<=N; i++)
		c[i][0]=0;
	for(j=0; j<=N; j++)
		c[0][j]=0;

	for(i=1; i<=N; i++)
		for(j=1; j<=N; j++)
			if(sorted[i-1]==unsort[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
			}
			else
			{
				c[i][j]=c[i][j-1];
			}

	return c[N][N];
}

int fun_name(  const void *a, const void *b )
{
	long *p = (long *)a;  
	long *q = (long *)b;  
	
	return *q - *p ;   
}

int main()
{
	long n, ii, height, testcase=1;

	while(1)
	{
		scanf("%ld", &n);
		if(n<0)
			break;
		else
		{
			unsort[0]=n;
			sorted[0]=n;

			ii=1;
			while(1)
			{
				scanf("%ld", &n);
				if(n<0)
					break;
				else
				{
					sorted[ii]=n;
					unsort[ii]=n;
					ii++;
				}
			}
		}

		N=ii;

		qsort( sorted, N, sizeof(long), fun_name );
		height=LCS_LENGTH();

		printf("Test #%ld:\n",testcase);
		printf("  maximum possible interceptions: %ld\n\n",height);
		testcase++;
	}
	return 0;
}

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;

int t,N,L,S[3000005],T;
vector <int> V;
bool flag;

int main(){
	while(scanf("%d",&t) == 1){
		if(t != -1) V.push_back(t);
		else{
			if(V.empty()) break;
			N = V.size();
			reverse(V.begin(),V.end());
			L = 0;
			for(int i=0;i<N;++i){
				if(!L){
					S[0] = V[i];
					L = 1;
				}
				else{
					t = upper_bound(S,S+L,V[i])-S;
					S[t] = V[i];
					L = max(t+1,L);
				}
			}
			printf("Test #%d:\n",++T);
			printf("  maximum possible interceptions: %d\n",L);
			V.clear();
		}
	}
}