POJ1065

POJ1065

http://poj.org/problem?id=1065

DP問題の練習です。 ソートして順次大きい方からつなげていけば終わりです。

久しぶりだったのでc++のいろいろな書き方忘れちゃって時間かかりました。

あと、終わってから気づいたのですが、subsetはvectorである必要ないですね。

解答時間は1時間です。

以下コードです。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int,int> s;
vector<s> stick;
vector<s> subset;
int t, n;
int w,l;
bool flag = false;

void init(){
  vector<s> empty1;
  vector<s> empty2;
  swap(stick, empty1);
  swap(subset, empty2);
}

bool comp(const s &a, const s &b){
  return a.second > b.second;
}

int solve(){
  for(int i = 0; i < n; i++){
    flag = false;
    sort(subset.begin(), subset.end(), comp);
    for(int j = 0; j < subset.size(); j++){
      if(subset[j].second <= stick[i].second){
        subset[j].second = stick[i].second;
        flag = true;
        break;
      }
    }
    if(!flag){
      subset.push_back(stick[i]);
    }
  }
  return subset.size();
}

int main(){
  scanf("%d",&t);
  for(int i = 0; i < t; i++){
    scanf("%d", &n);
    for(int j = 0; j < n; j++){
      scanf("%d %d", &l, &w);
      stick.push_back(s(l,w));
    }
    sort(stick.begin(), stick.end());
    printf("%d\n", solve());
    init();
  }
  return 0;
}