Ribbon on the Christmas Present
Source: aizu

Ribbon on the Christmas Present

You are preparing a ribbon to decorate the Christmas present box. You plan to dye the ribbon, initially white, to make a stripe pattern of different shades of red. The ribbon consists of a number of sections, each of which should be dyed as planned.

You want to prepare the ribbon with the least number of dyeing steps. Contiguous sections of the ribbon can be dyed in one step with the same shade of red. A ribbon section already dyed with some shade of red can be overdyed with dyestuff of a darker shade; it is colored with that darker shade. Overdyeing with a lighter shade is, however, not allowed. As the ribbon is initially white, all the sections must be dyed at least once.


Figure A.1. Stripe Pattern of Sample Input 1


Figure A.1 shows the pattern of Sample Input 1. The ribbon has six sections and the numbers in the sections mean the levels of shades to be dyed. Larger numbers mean darker shades. This can be made by three dyeing steps:

dye the entire ribbon with red dyestuff of shade level 50,
dye the second section from the left with darker shade dyestuff of level 100, and then
dye the fifth section with dyestuff of level 100.

Write a program that computes the least number of dyeing steps to make the planned stripe pattern.

Input

The input consists of a single test case of the following format.

n
d1 d2 ... dn


The test case starts with an integer n (1≤n≤100), the number of sections of the ribbon. The second line contains n integers, d1,d2,...,dn, describing the planned shade levels of the n sections. Here, di means the planned shade level of the i-th section, which is between 1 and 100, inclusive, larger meaning darker.

Output

Output a line containing the least number of dyeing steps to make the planned stripe pattern.

Sample Input 1
6
50 100 50 50 100 50

Sample Output 1
3

Sample Input 2
5
1 2 3 2 1

Sample Output 2
3

Sample Input 3
5
3 2 1 2 3

Sample Output 3
5

Sample Input 4
10
1 20 100 1 20 20 100 100 20 20

Sample Output 4
5

Sample Input 5
5
10 60 100 30 10

Sample Output 5
4


C++ solution:
#include<bits/stdc++.h>
#define rep(i,j,n) for(ll i=j;i<(ll)(n);i++)
#define rrep(i,j,n)  for(ll i=j;i>=n;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define pb push_back
#define mp make_pair
#define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end())

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template<class T> bool chmax(T &a, const T &b){if(a<b) {a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b){if(a>b) {a=b;return 1;}return 0;}
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void yn(bool ok){
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

void solve(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,0,n) cin >> a[i];
    vector<vector<ll>> table(110);
    rep(i,0,n){
        table[a[i]].pb(i);
    }
    ll ans = 0;
    rep(i,1,101){
        if(table[i].empty()) continue;
        ll l=table[i][0],r=table[i][table[i].size()-1];
        ans++;
        bool in = false;
        rep(j,l,r+1){
            if(a[j] < i && in){
                ans++;
                in=false;
            }
            if(a[j] == i)
                in=true;
        }
    }
    cout << ans << endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    /*
    ll T;
    cin >> T;
    while(T--) 
    */
    solve();
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	line := scanner.Text()
	parts := strings.Fields(line)
	A := make([]int, n)
	for i := 0; i < n; i++ {
		num, _ := strconv.Atoi(parts[i])
		A[i] = num
	}

	var makeFunc func(l, r int) int
	makeFunc = func(l, r int) int {
		if l >= r {
			return 0
		}
		m := math.MaxInt32
		for i := l; i < r; i++ {
			if A[i] < m {
				m = A[i]
			}
		}
		res := 0
		pre := l
		for i := l; i < r; i++ {
			if A[i] == m {
				if pre < i {
					res += makeFunc(pre, i)
				}
				pre = i + 1
			}
		}
		if pre < r {
			res += makeFunc(pre, r)
		}
		return res + 1
	}

	fmt.Println(makeFunc(0, n))
}

Java solution:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
        System.out.println(make(0, n, A));
    }

    private static int make(int l, int r, int[] A) {
        if (l >= r) return 0;
        int m = Integer.MAX_VALUE;
        for (int i = l; i < r; i++) {
            if (A[i] < m) {
                m = A[i];
            }
        }
        int steps = 1;
        int now = l;
        while (now < r) {
            if (A[now] == m) {
                now++;
                continue;
            }
            int l1 = now;
            while (now < r && A[now] != m) {
                now++;
            }
            steps += make(l1, now, A);
        }
        return steps;
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
let currentLine = 0;

rl.on('line', (line) => {
    inputLines.push(line);
}).on('close', () => {
    const n = parseInt(inputLines[0]);
    const A = inputLines[1].split(' ').map(num => parseInt(num));
    
    const make = (l, r) => {
        if (l >= r) return 0;
        let m = Infinity;
        for (let i = l; i < r; i++) {
            if (A[i] < m) {
                m = A[i];
            }
        }
        let steps = 1;
        let now = l;
        while (now < r) {
            if (A[now] === m) {
                now++;
                continue;
            }
            let l1 = now;
            while (now < r && A[now] !== m) {
                now++;
            }
            steps += make(l1, now);
        }
        return steps;
    };
    
    console.log(make(0, n));
});

Python solution:
n = int(input())
A = list(map(int, input().split()))

ans = 0

from sys import setrecursionlimit as srl
srl(10**6)
def make(l, r):
  global ans
  m = float("INF")
  for i in range(l, r):
    m = min(m, A[i])
  pre = m
  now = l
  temp = 1
  while now < r:
    if A[now] == m:
      now += 1
      continue
    l1 = now
    while now < r and A[now] != m:
      now += 1
    temp += make(l1, now)
  return temp
  
print(make(0, n))

Ruby solution:
n = gets.to_i
arr = gets.chomp.split.map(&:to_i)

temp = [[arr[0]]]
arr.each_cons(2){|a, b| temp[0] << b if a != b}

count = 0
while arr = temp.pop
    count += 1
    temp2 = []
    min = arr.min
    arr.each{|v|
        if v > min
            temp2 << v
        else
            if !temp2.empty?
                temp << temp2
                temp2 = []
            end
        end
    }
    temp << temp2 if !temp2.empty?
end
puts count