OJ Board

Code: Select all

CUT AFTER ACCC.......

Code: Select all

int Data[10001],n,DP[10001],a[10001],DP1[10001];         // I change you array size to 10001

void LIS()
{
	int i,j,s,x=0;
	memset(DP,0,sizeof(DP));
	memset(DP1,0,sizeof(DP1));
	DP[0] = DP1[0] = a[0];
	maxv = maxd = a[0];
	for(i=1;i<n;i++)
	{
		s = 0;
		DP[i]=DP1[i]=a[i];            //be care of here !!! the width maybe negetive...or am I misunderstand it?
		for(j=i-1;j>=0;j--)

Code: Select all

#include<stdio.h>

#define size 10001
typedef struct{
	long index;
	long a;
}data;
data I[size],D[size];
int main(){
	long i,j,n,T,cas=1,height[size],temp[size],max_i,max_d,max;
	
	//freopen("i.txt","r",stdin);
	
	scanf("%ld",&T);
	while(T--){
		printf("Case %ld. ",cas++);
		
		
		scanf("%ld",&n);
		for(i=0;i<n;i++){
			scanf("%ld",&height[i]);
		}			
		for(i=0;i<n;i++){
			scanf("%ld",&temp[i]);
			I[i].a=D[i].a=temp[i];			
			I[i].index=D[i].index=1;
		}
		max=temp[0];

		for(i=1;i<n;i++){
			if(max<temp[i])
				max=temp[i];
		}
		max_i=max_d=max;
		
		for(i=0;i<n-1;i++){
			for(j=i+1;j<n;j++){
				if(height[j]>height[i]){					
					if(I[i].index+1>I[j].index){
						I[j].index=I[i].index+1;
						I[j].a=I[i].a+temp[j];
						if(max_i<I[j].a)
							max_i=I[j].a;
						
					}					
					else if(I[i].index+1 == I[j].index){						
						if(I[i].a+temp[j]>I[j].a)
							I[j].a=I[i].a+temp[j];
						if(max_i<I[j].a)
							max_i=I[j].a;
						
					}
				}				
				else if(height[j]<height[i]){					
					if(D[i].index+1>D[j].index){
						D[j].index=D[i].index+1;
						D[j].a=D[i].a+temp[j];
						if(max_d<D[j].a)
							max_d=D[j].a;
						
					}
					else if(D[i].index+1 == D[j].index){						
						if(D[i].a+temp[j]>D[j].a)
							D[j].a=D[i].a+temp[j];
						if(max_d<D[j].a)
							max_d=D[j].a;
						
					}
				}			
			}
		}		
		if(max_i>=max_d)
			printf("Increasing (%ld). Decreasing (%ld).\n",max_i,max_d);
		else
			printf("Decreasing (%ld). Increasing (%ld).\n",max_d,max_i);
		}
		return 0;
}

Code: Select all

1
3
1 2 3
1 -10 2

Code: Select all

Case 1. Increasing (3). Decreasing (2).

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 10001

long A[MAXN],N,B[MAXN];
long L[MAXN],P1[MAXN],P2[MAXN],waitSum1[MAXN],waitSum2[MAXN],last1,last2,lis,lds,D[MAXN];

void doLIS() 
{
	long i, j;
	long longest1 = 0,longest2=0;
	lis=lds=last1=last2=0;
	for(i = 1; i<=N; i++) 
	{
		long max1 = 0,max2=0;
		long parent1 = -1,parent2=-1;
		for(j = i-1; j>=0; j--) 
		{
			if(B[i]<0)	break;
			if(A[i] > A[j]) 
			{
				if(L[j] > max1) 
				{
					max1 = L[j];
					parent1 = j;
				}
				else if(L[j]==max1 && parent1!=-1)
				{
					if(waitSum1[j]>waitSum1[parent1])
						parent1=j;
				}
			}
			else if(A[i] < A[j])
			{
				if(D[j] > max2) 
				{
					max2 = D[j];
					parent2 = j;
				}
				else if(D[j]==max2 && parent2!=-1)
				{
					if(waitSum2[j]>waitSum2[parent2])
						parent2=j;
				}	
			}
		}

		L[i] = max1+1;
		P1[i] = parent1;
		D[i]=max2+1;
		P2[i]=parent2;
		if(parent1==-1)
			waitSum1[i]=B[i];
		else
		{
			waitSum1[i]=B[i]+waitSum1[parent1];
		}
		if(parent2==-1)
			waitSum2[i]=B[i];
		else
		{
			waitSum2[i]=B[i]+waitSum2[parent2];
		}

		if(lis<waitSum1[i])
			lis=waitSum1[i];
		if(lds<waitSum2[i])
			lds=waitSum2[i];

		if(L[i] > longest1) 
		{
			longest1 = L[i];
			last1 = i;
		}
		else if(L[i]==longest1)
		{
			if(waitSum1[i]>waitSum1[last1])
				last1=i;
		}
		if(D[i] > longest2) 
		{
			longest2 = D[i];
			last2 = i;
		}
		else if(D[i]==longest2)
		{
			if(waitSum2[i]>waitSum2[last2])
				last2=i;
		}
	}
}

int main() 
{
	long i,kase=1,T;
	cin>>T;
	while(T--) 
	{
		cin>>N;
		A[0] = 0;
		for(i = 1; i<= N; i++) 
		{
			cin>>A[i];
		}
		for(i = 1; i<= N; i++) 
		{
			cin>>B[i];
		}
		cout<<"Case "<<kase++<<". ";
		doLIS();
		if(lis>=lds)
			cout<<"Increasing ("<<lis<<"). Decreasing ("<<lds<<").\n";
		else
			cout<<"Decreasing ("<<lds<<"). Increasing ("<<lis<<").\n";
	}
	return 0;
}