Giải bài ntucoder LUDI - Lưu diễn

Link bài:

Cách 1:

Thuật toán:

• Sắp xếp các buổi diễn theo thứ tự tăng dần của giờ bắt đầu.
  
• Ta dùng đệ quy để giải quyết vấn đề.
  
• Với buổi diễn thứ i, ta sẽ tìm buổi diễn thứ j (j < i) thỏa giờ bắt đầu buổi diễn thứ j không được sớm hơn giờ kết thúc buổi diễn thứ i. Lặp lại với buổi diễn thứ j và ta sẽ tổng lại rồi lưu giá trị lớn nhất có được.
  
  • Lưu ý: Do test không phức tạp, nên ta có thể tham lam và đệ quy thay vì dùng quy hoạch động.

Code:

Mã:

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

pair <int, int> a[1007];
long long int n, ans;

long long int brow(int pos){
    for (int i = pos - 1; i >= 1; i--)
        if (a.se < a[pos].fi) return 1 + brow(i);
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("ludi.inp", "r", stdin);
    //freopen("ludi.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a.fi >> a.se;
    sort(a+1, a+n+1);
    for (int i = n; i >= 1; i--) ans = max(ans, brow(i));
    cout << ans;
    //cout << endl;
    //for (int i = 1; i <= n; i++) cout << a.fi << " " << a.se << endl;

    return 0;
}

Cách 2:

Thuật toán:

• Ta để ý thời gian kết thúc của buổi diễn càng sớm thì số lượng buổi diễn phía sau tham dự được càng nhiều. Tức là những buổi diễn có giờ kết thúc sớm hơn sẽ có khả năng được chọn hơn.
  
• Sắp xếp các buổi diễn theo thứ tự tăng dần của thời điểm kết thúc.
  
• Ta lựa chọn các buổi diễn với thời gian bắt đầu không sớm hơn thời gian kết thúc của buổi diễn trước. Đồng thời có thời gian kết thúc sớm.

Code:

Mã:

#include <bits/stdc++.h>
#define repinc(k, n) for (int i = k; i <= n; i++)
#define repdec(n, k) for (int i = n; i >= k; i--)
#define ii pair <int, int>
#define fi first
#define se second
#define oo 1e18
using namespace std;

int n, Min = -oo, ans = 0;
pair <int, int> a[1007];

void read(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("LUDI.INP", "r", stdin);
    //Freopen("LUDI.OUT", "w", stdout);
    cin >> n;
    repinc(1, n){
        cin >> a.se >> a.fi;
       // cout << ans << " ";
    }
}

void run(){
    sort(a+1, a+n+1);
    for (int i = 1; i <= n; ++i){
        if (a.se > Min){
            Min = a.fi;
            ans++;
        }
    }
  //  cout << "\n";
  //  repinc(1, n) cout << a.fi << " " << a.se << "\n";
    cout << ans;
}
int main(){
    read();
    run();

    return 0;
}