Editorial for Cho thỏ vào hang
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtest 01
Giải pháp brute-force ngây thơ sẽ liệt kê tất cả các cách phù hợp có thể giữa thỏ và hang, mất thời gian \(O(N!⋅N\)).
Subtest 02
Để có một giải pháp chạy trong thời gian đa thức, Hiếu có thể bắt đầu bằng việc sắp xếp thỏ và hang theo kích thước tăng dần. Hiếu xác định thỏ nhỏ nhất chưa được gán hang, sau đó đếm số cách phù hợp thỏa điều kiện này trong thời gian \(O(N^2)\) bằng cách dùng quy hoạch động, lưu trữ số lượng thỏ/hang đã xử lý cùng với số lượng thỏ cần được gán trong phù hợp cuối cùng.
Khi xử lý một con thỏ, Hiếu có thể chọn gán nó vào hang hoặc không. Nếu gán, số lượng thỏ cần phù hợp tăng lên một. Thỏ nhỏ hơn thỏ nhỏ nhất chưa gán phải được gán.
Khi xử lý một cái hang, Hiếu có thể cố gắng gán nó cho một con thỏ cần phù hợp hoặc không. Hang lớn hơn thỏ nhỏ nhất chưa gán phải được gán.
Phương pháp này sẽ mất thời gian \(O(N^3)\).
Subtest 03
Để tối ưu hóa xuống còn \(O(N^2)\), thay vì lặp qua tất cả thỏ nhỏ nhất có thể không được gán, Hiếu giữ thêm một thông tin trong trạng thái quy hoạch động của mình: một flag boolean cho biết liệu tất cả thỏ đã xem đến nay sẽ được gán vào hang hay không. Khi quyết định không gán một con thỏ, Hiếu đặt cờ này thành true. Chỉ khi cờ là false, Hiếu mới quyết định không gán một cái hang (vì nếu không, có thể gán thỏ không được chọn vào hang hiện tại).
Cuối cùng, giải pháp quy hoạch động này có \(O(N^2)\) trạng thái và O(1) chuyển đổi cho mỗi trạng thái, dẫn đến thời gian chạy mong muốn là \(O(N^2)\). Kết quả cuối cùng của số lượng phù hợp sẽ được lấy mod 10^9+7 để đảm bảo số không quá lớn.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
const int MOD = 1000000007;
struct Event {
int size, type;
Event(int size, int type) : size(size), type(type) {}
bool operator<(const Event& e) const {
if (size != e.size) return size < e.size;
return type < e.type;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int n;
cin >> n;
vector<Event> events;
for (int a = 0; a < 2; a++) {
for (int i = 0; i < n; i++) {
int x;
cin >> x;
events.push_back(Event(x, a));
}
}
sort(events.begin(), events.end());
vector<vector<int>> dp(n+1, vector<int>(2, 0)), ndp(n+1, vector<int>(2, 0));
dp[0][0] = 1;
for (Event e : events) {
for (int i = 0; i <= n; i++) fill(ndp[i].begin(), ndp[i].end(), 0);
if (e.type == 0) {
// rabbit
for (int a = 0; a < n; a++) {
for (int j = 0; j < 2; j++) {
ndp[a+1][j] = (ndp[a+1][j] + dp[a][j]) % MOD;
ndp[a][1] = (ndp[a][1] + dp[a][j]) % MOD;
}
}
} else {
// cave
for (int a = 0; a < n; a++) {
if (a > 0) {
for (int j = 0; j < 2; j++) {
ndp[a-1][j] = (ndp[a-1][j] + a * 1LL * dp[a][j] % MOD) % MOD;
}
}
ndp[a][0] = (ndp[a][0] + dp[a][0]) % MOD;
}
}
dp = ndp;
}
cout << (dp[0][0] + dp[0][1]) % MOD << endl;
return 0;
}
Comments