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

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/BAT2/

#include <iostream>
using namespace std;
int n, t, arr[105], z[105][105];
 
int main() {
    cin >> t;
    while(t--){
        cin >> n;
 
        for(int i = 1; i <= n ; i++){
            cin >> arr[i];
        }
 
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j <= n; j++){
                z[i][j] = -1410065408;
            }
        }
 
        z[0][0] = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= i - 1; ++j){
                if(j == 0 || arr[j] < arr[i]){
                    if(z[j][0] + 1 > z[i][0]){
                        z[i][0] = z[j][0] + 1;
                    }
                }
            }
        }
 
        for(int j = 1; j <= n; ++j){
            for(int k = 0; k <= j - 1; ++k){
                if(k == 0 || arr[k] > arr[j]){
                    if(z[0][k] + 1 > z[0][j]){
                        z[0][j] = z[0][k] + 1;
                    }
                }
            }
        }
 
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(i == j){
                    continue;
                }
                if(i > j){
                    for(int k = 0; k <= i - 1; ++k){
                        if(k == 0 || arr[k] < arr[i] && z[k][j] > -1410065408){
                            if(z[k][j] + 1 > z[i][j]){
                                z[i][j] = z[k][j] + 1;
                            }
                        }
                    }
                }else if(j > i){
                    for(int k = 0; k <= j - 1; ++k){
                        if(k == 0 || arr[k] > arr[j] && z[i][k] > -1410065408){
                            if(z[i][k] + 1 > z[i][j]){
                                z[i][j] = z[i][k] + 1;
                            }
                        }
                    }
                }
            }
        }
 
        int ans = -1410065408;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                ans = max(z[i][j], ans);
            }
        }
 
        cout << ans << endl;
    }
 
    return 0;
}