TIOJ 1501 . Dead at the end of sixth sense

枚舉最小值

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long int int64;

const int64 inf = 10000000000LL;

int64 iabs(int64 a){return max(a, -a);}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        int64 arr[1001];
        for(int lx = 0;lx < n;lx++) scanf("%lld", arr+lx);
        int64 ans = inf;
        for(int lx = 0;lx < n;lx++){
            int64 tab[1001];
            for(int ly = 0;ly < n;ly++) tab[ly] = inf;
            tab[n-1] = arr[n-1], tab[n] = arr[n-1];
            arr[n] = arr[n-1];
            for(int ly = n-2;ly>=0;ly--){
                if(arr[ly] < arr[lx]) continue;
                int64 mm = inf;
                if(arr[ly+1] >= arr[lx]) mm = min(mm, tab[ly+1]);
                if(arr[ly+2] >= arr[lx]) mm = min(mm, tab[ly+2]);
                tab[ly] = max(arr[ly], mm);
            }
            int64 cal = tab[0]-arr[lx];
//            printf("%d -> cal = %lld\n", lx, cal);
            ans = min(tab[0]-arr[lx], ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}