uva1608 Non-boring sequences

某个序列找到唯一元素后，判断被分成的两边的序列即可
问题在于找到唯一元素
连续序列，重复元素的问题；感觉很有一般性 查找相同元素用map，last，next存上一个相同元素的位置
复杂度计算有点思考；
记录last，next，那么对于一个元素，判断是否独立O（1）
从头开始查找，最坏情况T（n）=T（n-1）+O（n）（O（n）是从头判断到尾） =O（n^2）
两边开始T（n）=2T（n/2）+O（n）=T（nlogn）

#include<cstdio>

#include<map>

using namespace std;

const int maxn =  + ;

int A[maxn], last[maxn], nextp[maxn];

map<int, int> cur;

bool duli(int p, int L, int R) {

  return last[p] < L && nextp[p] > R;

}

bool check(int L, int R) {

  if(L >= R) return true;

  for(int d = ; L+d <= R-d; d++) {

    if(duli(L+d, L, R))                        //L+d位置上的元素 独立

      return check(L, L+d-) && check(L+d+, R);

    if(L+d == R-d) break;

    if(duli(R-d, L, R))

      return check(R-d+, R) && check(L, R-d-);

  }

  return false;

}

int main() {

  int T, n;

  scanf("%d", &T);

  while(T--) {

    scanf("%d", &n);

    cur.clear();

    for(int i = ; i < n; i++) {

      scanf("%d", &A[i]);

      if(!cur.count(A[i]))

        last[i] = -;

      else

        last[i] = cur[A[i]];

      cur[A[i]] = i;

    }

    cur.clear();

    for(int i = n-; i >= ; i--) {

      if(!cur.count(A[i]))

        nextp[i] = n;

      else

      nextp[i] = cur[A[i]];

      cur[A[i]] = i;

    }

    if(check(, n-))

        printf("non-boring\n");

    else

        printf("boring\n");

  }

  return ;

}