Hướng dẫn giải của Làm lồng đèn
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Subtask 1
Thử cắt ~a_1~ trước rồi cắt ~a_2~, sau đó thử cắt ~a_2~ rồi ~a_1~. Xem cách cắt nào tối ưu hơn.
Subtask 2
Ta thêm ~a_0=0~ và ~a_{n+1} = l~
Gọi hàm solve(l, r) là tổng sức ít nhất để cắt đoạn tre từ vị trí ~a_l~ đến ~a_r~ (như vậy các vị trí ~a_l~ và ~a_r~ là đầu mút đoạn tre nên không cắt hai vị trí này).
Hàm solve được cài đặt như sau:
int solve(int l, int r) {
if (l == r || l+1 == r) return 0;
int ans = 1e9;
FOR(k, l+1, r-1) {
minimize(ans, solve(l, k) + solve(k, r) + a[r]-a[l]);
}
return ans;
}
Đáp án của bài toán chính là giá trị của hàm solve(0, n+1).
Độ phức tạp ~O(n!)~.
Subtask 3
Ta thấy một hàm solve(l_1, r_1) có thể được gọi nhiều hơn ~1~ lần.
Vì vậy ta đưa về mảng quy hoạch động: gọi ~dp[i][j]~ là tổng sức ít nhất để cắt đoạn tre với hai dầu mút ở vị trí ~a_i~ và ~a_j~.
Độ phức tạp ~O(n^3)~.
Code tham khảo:
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n, l;
const int N = 52;
int a[N];
int dp[N][N];
void Input() {
cin >> l;
cin >> n;
a[0] = 0;
FOR(i, 1, n) cin >> a[i];
a[n+1] = l;
}
int solving(int l, int r) { // subtask 2
if (l == r || l+1 == r) return 0;
int ans = 1e9;
FOR(k, l+1, r-1) {
minimize(ans, solving(l, k) + solving(k, r) + a[r]-a[l]);
}
return ans;
}
void Solve() {
memset(dp, 0x3f, sizeof dp);
FORD(i, n+1, 0)
FOR(j, i, n+1) {
if (i == j || i+1 == j) dp[i][j] = 0;
else FOR(k, i+1, j-1) minimize(dp[i][j], dp[i][k] + dp[k][j] + a[j]-a[i]);
}
cout << dp[0][n+1];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
Input(), Solve();
return 0;
}
Bình luận