UVa-496 Simply subsets

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

#define MAX 1000
int M,N,LCS[1000+5][1000+5];

class set{
    public:
int element[MAX];
int card;
};

int lcs(set A,set B)
{ int M=A.card,N=B.card;
int i,j;
for(i=0;i<1005;i++)LCS[i][0]=0;
for(j=0;j<1005;j++)LCS[0][j]=0;

for(i=1;i<=M;i++)
    for(j=1;j<=N;j++)
    {
        if(A.element[i-1]==B.element[j-1])LCS[i][j]=LCS[i-1][j-1]+1;
      else LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
    }
return LCS[M][N];
}
void print(int res,int M,int N)
{  if(res==0)cout<<"A and B are disjoint"<<endl;
    else if(M!=N){if(res==M)cout<<"A is a proper subset of B"<<endl;
                    else if(res==N)cout<<"B is a proper subset of A"<<endl;
                    else cout<<"I'm confused!"<<endl;
                    }
     else if(M==N){if(res==M)cout<<"A equals B"<<endl;
                    else cout<<"I'm confused!"<<endl;

                      }
      return ;
}


int main()
{
    while(1){ set S[2];
                  M=N=0;
                    char inp1[MAX],inp2[MAX];
                    gets(inp1);
                    if(feof(stdin))break;
                    char *p1;
                    p1=strtok(inp1," ");
                     while(p1!=NULL){ S[0].element[M++]=atoi(p1);
                                                    p1=strtok(NULL," ");
                                                    }
                                                    S[0].card=M;

                    gets(inp2);
                    char *p2;
                    p2=strtok(inp2," ");
                     while(p2!=NULL){ S[1].element[N++]=atoi(p2);
                                                    p2=strtok(NULL," ");
                                                    }
                                                    S[1].card=N;
                       sort(S[0].element,S[0].element+M);
                       sort(S[1].element,S[1].element+N);
                       int res=lcs(S[0],S[1]);

                       print(res,M,N);
                       }
                       return 0;
}

UVa-482 Permutation arrays

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


class array{
public:int i;
string num;
};

bool comp(array a,array b)
{
    if(a.i<b.i)return true;
    else return false;
}
int main()
{ int test;
scanf("%d",&test);
array a[1000];
bool blank=false;
getchar();
while(test--){char input[100000];

                    gets(input);
                     gets(input);
                     char *point;
                     int index1=0,index2=0;
                    point=strtok(input, " ");
                    while(point!=NULL){a[index1++].i=atoi(point);
                                                        point=strtok(NULL, " ");

                                                        }
                                   gets(input);
                           point=strtok(input," ");
                    while(point!=NULL){a[index2++].num=point;
                                                        point=strtok(NULL," ");
                                                        }
                    sort(a,a+index1,comp);
                    if(blank)cout<<endl;
                    blank=true;
                    for(int I=0;I<index1;I++)cout<<a[I].num<<endl;
                           }

}

UVa-10131 Is bigger smarter?

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
#define MAX 10000
int I,len[MAX],pre[MAX],output[MAX],i,j,maX,highest;


class elephant{
public:
int iq,weight,index;
};

bool comp(elephant a,elephant b)
{
    if (a.iq>=b.iq)return true;
    else return false;
}



int main()
{
    int W,IN=0;
    I=0;
    elephant ele[MAX];
    while(scanf("%d %d",&W,&IN)!=EOF)
    {ele[I].weight=W;
      ele[I].iq=IN;
      ele[I].index=I+1;
      I++;

    }
    sort(ele,ele+I,comp);
    //int res=lis(I);
    for(i=0;i<I;i++){pre[i]=i;len[i]=1;}
    for(i=0;i<I-1;i++)
       for(j=i+1;j<I;j++)
           {
                    if(ele[i].weight<ele[j].weight && len[i]+1>len[j]){len[j]=len[i]+1;pre[j]=i;}
           }
     maX=0;
     for(i=0;i<I;i++)if(maX<len[i]){maX=len[i];highest=i;}
     cout<<maX<<endl;
//output
for(i=maX;i>0;i--){output[i]=highest;
                                 highest=pre[highest];
                                 }
         for(i=1;i<=maX;i++)cout<<ele[output[i]].index<<endl;
 
  return 0;
}

UVa-497 Strategic Defense Initiative

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

#define MAX 10000

int len[MAX+5],pre[MAX+5],seq[MAX+5],output[MAX+10];
int N,maX,highest;

int lis(int N)
{
    int i,j;
    for(i=0;i<N;i++)len[i]=1;

    for(i=0;i<N;i++)
       for(j=i+1;j<N;j++){if(seq[j]>seq[i]){ if(len[i]+1>len[j]){len[j]=len[i]+1;
                                                                                                   pre[j]=i;
                                                                                                      }

                                                                     }
       }
       maX=0;
   for(i=N-1;i>=0;i--){if(maX<len[i]){maX=len[i];highest=i;}
                                      }

       return maX;
}

void printlcs()
{  output[maX]=seq[highest];
    for(int i=maX-1;i>0;i--){ output[i]=seq[pre[highest]];
                                               highest=pre[highest];
                                                  }
for(int i=1;i<=maX;i++)cout<<output[i]<<endl;

return ;
}


int main()
{
    int tc,t=0;
    scanf("%d",&tc);
    getchar();
    char ch[20];
    bool blank=false;

    gets(ch);
    while(tc--){int I=0;
    while(gets(ch) &&strlen(ch))
    {

         //puts(ch);
                                                     int J=atoi(ch);
                                                     seq[I++]=J;
                                                     //cout<<J<<endl;




    }
    //cout<<I<<endl;
    if(blank)cout<<endl;
    blank=true;
    int res=lis(I);
    printf("Max hits: %d\n",res);
    printlcs();

}
return 0;
}