11790 - Murcia's Skyline

#include<iostream>
#include<vector>
#include<cstdio>
#define MAXNEG -2134483648
using namespace std;

vector< int > Height,Width;
vector< int > Len;

int LIS(int,int);

int main()
{
    int t,n,i,k,a,b;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    for(k=1;k<=t;k++)
    {
        scanf("%d",&n);

        Height = vector < int >(n+1);
        Width = vector < int >(n+1);
       
        Length = vector < int >(n+1);

        for(i=1;i<=n;i++)
            scanf("%d",&Height[i]);

        for(i=1;i<=n;i++)
            scanf("%d",&Width[i]);

        a = LIS(n,1);
        b = LIS(n,-1);

        if(a>=b)
            printf("Case %d. Increasing (%d). Decreasing (%d).\n",k,a,b);
        else
            printf("Case %d. Decreasing (%d). Increasing (%d).\n",k,b,a);
    }
    return 0;
}

int LIS(int n,int f)
{
    int i,k,tmp;
    Len = vector < int >(n+1);
    for(i=0;i<=n;i++)
        Len[i] = 0;

    if(f==-1)
    {
        Height[0] = MAXNEG;
        for(i=1;i<=n;i++)
            Height[i] = -Height[i];
    }

    for(k = 1;k <= n; k++)
    {
        for(i = k-1; i>=0; i--)
        {
            tmp = Width[k] + Len[i];
            if(Height[k]>Height[i] && Len[k] < tmp)
                Len[k] = tmp;
        }
    }

    tmp = Len[1];
    for(i=2;i<=n;i++)
        if(tmp < Len[i])
            tmp = Len[i];
    return tmp;
}