Menu

SPOJ BORW – Black or White

January 1, 2017 - SPOJ

Language: C++

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define MAX 202
#define inf 1000000000
using namespace std;
int dp[MAX][MAX][MAX];
int a[MAX],n;
int sol;
/*
int fun(int dec, int inc, int i) {
    if (dp[dec][inc][i] != -1) return dp[dec][inc][i];
    if (i == n) return 0;

    if (a[i] < a[dec]) {
        dp[dec][inc][i] = fun(i, inc, i+1);
    }
    if (a[i] > a[inc]) {
        if (dp[dec][inc][i] == -1)
            dp[dec][inc][i] = fun(dec, i, i+1);
        else
            dp[dec][inc][i] = min(fun(dec, i, i+1), dp[dec][inc][i]);
    }

    if (dp[dec][inc][i] == -1)
        dp[dec][inc][i] = 1 + fun(dec, inc, i+1);
    else
        dp[dec][inc][i] = min(1 + fun(dec, inc, i+1), dp[dec][inc][i]);

    return dp[dec][inc][i];
}
*/
int fun(int dec,int inc,int i)
{
	if(dp[dec][inc][i]!=-1)
	return dp[dec][inc][i];

	if(i==n)
	return 0;

	if(a[dec]>a[i])
	dp[dec][inc][i]=fun(i,inc,i+1);
	
	if(a[inc]<a[i])
	{
		if(dp[dec][inc][i]==-1)
		dp[dec][inc][i]=fun(dec,i,i+1);
		else
		dp[dec][inc][i]=min(dp[dec][inc][i],fun(dec,i,i+1));
	}
	
	if(dp[dec][inc][i]==-1)
	{
		dp[dec][inc][i]=1+fun(dec,inc,i+1);
	}
	else
	{
		dp[dec][inc][i]=min(1+fun(dec,inc,i+1),dp[dec][inc][i]);
	}

	return dp[dec][inc][i];
}
/*

int main() {
    a[MAX - 2] = inf;
    a[MAX - 1] = -inf;
    while (true) {
        scanf("%d", &n);
        
        if (n == -1) return 0;

        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }

        memset(dp, -1, sizeof dp);

        sol = fun(MAX-2, MAX-1, 0);

        printf("%dn", sol);
    }
    
    return 0;
}
*/
int main()
{
a[MAX-2]=1000000000;
		a[MAX-1]=-1000000000;
	while(1)
	{
		sf("%d",&n);
		if(n==-1)
		return 0;
		for(int i=0;i<n;i++)
		sf("%d",&a[i]);
		memset(dp,-1,sizeof(dp));
		pf("%dn",fun(MAX-2,MAX-1,0));
	}
return 0;
}

(600)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on VK

Author of this post : Anuj Chauhan

Leave a Reply

Your email address will not be published. Required fields are marked *