Участник:Andriygav/BORW

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
 
#include <cstring>
#include <iostream>
using namespace std;
 
int a[256], dp[256][256][256];
 
int rek(int dec_idx, int inc_idx, int idx, int n){
 
    if(dp[dec_idx][inc_idx][idx] != -1){
    	return dp[dec_idx][inc_idx][idx];
    }
 
    if(idx == n){
    	return 0;
    }
 
    if(a[idx] < a[dec_idx]){
        dp[dec_idx][inc_idx][idx] = rek(idx, inc_idx, idx + 1, n);
    }
 
    if(a[idx] > a[inc_idx]){
        if(dp[dec_idx][inc_idx][idx] == -1){
            dp[dec_idx][inc_idx][idx] = rek(dec_idx, idx, idx + 1, n);
        }
        else{
            dp[dec_idx][inc_idx][idx] = min(rek(dec_idx, idx, idx + 1, n), dp[dec_idx][inc_idx][idx]);
        }
    }
 
    if (dp[dec_idx][inc_idx][idx] == -1){
        dp[dec_idx][inc_idx][idx] = 1 + rek(dec_idx, inc_idx, idx + 1, n);
    }
    else{
        dp[dec_idx][inc_idx][idx] = min(1 + rek(dec_idx, inc_idx, idx + 1, n), dp[dec_idx][inc_idx][idx]);
	}
    return dp[dec_idx][inc_idx][idx];
}
 
int main() {
    a[254] = 1073741824;
    a[255] = -1073741824;
    int n;
    cin >> n;
    while(n != -1){
 
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
 
        memset(dp, -1, sizeof dp);
        cout << rek(254, 255, 0, n) << endl;
        cin >> n;
    }
 
    return 0;
}