Is Bigger Smarter?

PC/UVa IDs: 111101/10131 题目描述

分析:此题同Edit Step Ladders类似(至少在解法思路上很相似):把大象按体重递增排序,然后从排序后的最后一只大象开始向前“反攻倒算”,总的时间复杂度在O(n^2)。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Elephant {
public:
  Elephant() {}

  Elephant(int aw, int as, int ai) : w(aw), s(as), i(ai) {}

  bool operator <(const Elephant & e) const {
    return w < e.w;
  }

  int w;  //weight
  int s;  //smartness
  int i;  //order
};

class Result {
public:
  Result() : max(0), next(0) {}

  bool operator <(const Result & r) const {
    return max < r.max;
  }

  int max;  //max number of elephant in seq
  int next; //next elephant number in seq
};

vector<int> max_seq(vector<Elephant> & ele) {
  int n = ele.size();
  vector<Result> results(n);
  sort(ele.begin(), ele.end());
  results[n - 1].max = 1;
  for (int i = n - 2; i >= 0; i--) {
    Elephant & e = ele[i];
    int max = 0;
    int maxi = 0;
    for (int k = i + 1; k < n; k++) {
      Elephant & e2 = ele[k];
      if (e.w < e2.w && e.s > e2.s && max < results[k].max) {
        max = results[k].max;
        maxi = k;
      }
    }
    results[i].max = max + 1;
    results[i].next = maxi;
  }
  //build path
  vector<Result>::iterator it = max_element(results.begin(), results.end());
  int next = it->next;
  vector<int> r;
  r.push_back(ele[it - results.begin()].i);
  while (next) {
    r.push_back(ele[next].i);
    next = results[next].next;
  }
  return r;
}

int main() {
  int w, s;
  int c = 0;
  vector<Elephant> ele;
  while (cin >> w >> s) {
    ele.push_back(Elephant(w, s, ++c));
  }
  vector<int> seq = max_seq(ele);
  cout << seq.size() << endl;
  for (int i = 0; i < seq.size(); i++)
    cout << seq[i] << endl;
  return 0;
}

《Is Bigger Smarter?》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>