Wednesday, March 7, 2012

[code] TIOJ-1240 LIS but not LIS

http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1240

先sort但記錄原順序

對於每個s[i]拿最近且比他大的點


#include <stdio.h>
#include <algorithm>
using namespace std;

pair<int, int> s[101];
int main()
{
 int n, i;
 scanf("%d", &n);
 for (i = 0; i < n; i++) {
  scanf("%d", &(s[i].first));
  s[i].second = i;
 }
 sort(s, s + n);
 int count = 0;
 bool update;
 pair<int, int> last;
 do {
  update = false;
  for (i = 0; i < n; i++) {
   if (s[i].first >= 0 && (!update ||
       s[i].second > last.second && s[i].first > last.first)) {
    last = s[i];
    s[i].first = -1;
    update = true;
   }
  }
  if (update) {
   count++;
  }
 } while (update);
 printf("%d\n", count);
 return 0;
}
 

No comments:

Post a Comment