高級
字母配對
思路
此題給定
採用 DFS + 記憶化搜尋 策略。定義狀態為各堆疊當前已取出的物品數量 id:
即以混合進位制(每維的進位基數為
定義 dp[id] 為從狀態 id 開始(即各堆疊分別已取出
其中 dfs(0)。
遞迴實作時,對所有可行的堆疊對 dp[id] 記錄該狀態下所有可行決策的最大值。使用記憶化陣列 dp(初始化為 -1)避免重複計算。
時間 / 空間複雜度:
- 狀態數:最多有
個狀態。在題目限制下(每個堆疊最多 12 個物品、 ),狀態數上界為 ;實際上題目保證「所有堆疊的物品總數 」,故可行狀態數遠小於此值。 - 單次狀態轉移:對每個狀態枚舉所有堆疊對
,共 對,每對常數時間判斷與轉移,故單狀態時間為 。 - 總時間複雜度:
,在題目規模下可接受。 - 空間複雜度:
用於儲存 dp陣列。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
vector<vector<char>> a;
vector<vector<int>> b;
vector<int> n, pos, dp, m;
int k;
int dfs(int id) {
if (dp[id] != -1) return dp[id];
int now = 0;
for (int i = 0;i < k;i++) if (pos[i] < n[i]) {
for (int j = i + 1;j < k;j++) if (pos[j] < n[j] and a[i][pos[i]] == a[j][pos[j]]) {
now = max(now, b[i][pos[i]++] + b[j][pos[j]++] + dfs(id + m[i] + m[j]));
pos[i]--, pos[j]--;
}
}
return dp[id] = now;
}
int main() {
IO
cin >> k;
a.resize(k), b.resize(k), n.resize(k), pos.resize(k), m.resize(k);
int t = 1;
for (int i = 0;i < k;i++) {
cin >> n[i];
a[i].resize(n[i]), b[i].resize(n[i]);
for (int j = 0;j < n[i];j++) cin >> a[i][j] >> b[i][j];
m[i] = t;
t *= n[i] + 1;
}
dp.resize(t, -1);
cout << dfs(0);
}列印工廠
思路
給定
核心策略:枚舉所有可能的任務排列順序(共
演算法流程:
-
排列枚舉:使用
next_permutation枚舉所有種任務排列順序(對陣列 v先排序,再反覆呼叫next_permutation直到回到初始狀態)。 -
二分搜尋間隔
:對每個排列,在 區間內二分搜尋最大可行間隔 。定義「可行」為:按照該排列順序依次執行任務,每兩個任務之間至少休息 秒,且所有任務都能在截止時間內完成。 -
可行性檢查:對固定的
,從頭到尾模擬任務執行: - 設
last為當前時間(初始為 0)。 - 對排列中的第
個任務( ): - 若
,先讓印刷機休息 秒: last += g。 - 更新開始時間為「當前時間」與「任務最早開始時間
」的較大值: last = max(last, s[i])。 - 檢查是否能在截止時間前完成:若
last + t[i] > d[i],則不可行(can = false)。 - 更新當前時間為任務結束時間:
last += t[i]。
- 若
- 若所有任務都通過檢查,則
可行,更新答案 ans = max(ans, g)並嘗試更大的( l = m + 1);否則縮小( r = m - 1)。
- 設
-
輸出最大值:所有排列檢查完畢後,輸出
ans。
時間 / 空間複雜度:
- 排列數:
;每個排列需二分搜尋 次( 為時間值域),每次檢查需 ;總時間複雜度為
在
- 空間用於儲存任務資訊與排列狀態,為
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO
int n;
cin >> n;
vector<array<int, 3>> v(n);
for (auto &[s, d, t] : v) cin >> s >> d >> t;
sort(v.begin(), v.end());
int ans = 0;
do {
int l = 0, r = 1000;
while (l <= r) {
int m = (l + r) / 2;
int last = 0;
bool can = 1;
for (int i = 0;i < n;i++) {
if (i) last += m;
last = max(last, v[i][0]);
if (last + v[i][2] > v[i][1]) {
can = 0;
break;
}
last += v[i][2];
}
if (can) ans = max(ans, m), l = m + 1;
else r = m - 1;
}
} while(next_permutation(v.begin(), v.end()));
cout << ans;
}翻來覆去
思路
給定長度為
核心觀察:要輸出遞增序列
資料結構與維護:
-
堆疊表示:不顯式儲存堆疊內容,而是用區間列表
s1與s2維護兩個堆疊當前擁有的連續區間(表示原始排列位置 到 的元素都在該堆疊)。堆疊頂部對應最後加入的區間;同一堆疊內各區間不重疊。 -
位置標記:使用 BIT(樹狀陣列) 進行區間加減,維護每個位置屬於哪個堆疊:
bit.get(p)返回 1 表示位置在 ,返回 0 表示在 。初始時所有位置標記為 1(全在 )。
演算法流程(按
-
查詢
與其所屬堆疊 ( from為當前堆疊,to為另一堆疊)。 -
堆疊頂部調整:若
from的最頂區間不包含 (即 ),表示該區間整體在 的上方,需先將其全部 pop(共 次)並推入 to,同時更新 BIT 標記;重複此步驟直到頂部區間包含。 -
取出目標元素:設頂部區間為
,根據堆疊類型分情況處理: -
若
( ,左側為頂):需 pop 出 共 個元素。若 ,將左側部分 推入 to;若,更新 from的頂部區間為,否則移除該區間。 -
若
( ,右側為頂):需 pop 出 共 個元素。若 ,將右側部分 推入 to;若,更新 from的頂部區間為,否則移除該區間。
-
-
累加 pop 次數到
ans。
時間 / 空間複雜度:
- 每個區間最多被建立與刪除各一次,總區間數
;每次查詢 BIT 與區間加減皆為 ;總時間複雜度為
- 空間用於 BIT 與區間列表,為
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
struct BIT{
int n; vector<int> b;
BIT(int n = 0) {init(n);}
void init(int x) {
n = x + 1;
b.assign(n + 2, 0);
}
void add(int i, int v) {
for (;i <= n;i += i & -i) b[i] += v;
}
void range_add(int l, int r, int v) {
if (l <= r) {
add(l, v);
add(r+1,-v);
}
}
int get(int i) {
int s = 0;
for (;i;i -= i & -i) s+=b[i];
return s;
} // 0=S1, 1=S2
};
int main() {
IO
int n;
cin >> n;
vector<int> pos(n + 1);
for (int i = 1, x;i <= n;i++) {
cin >> x;
pos[x] = i;
}
vector<pair<int, int>> s1, s2;
s2.push_back({1, n});
BIT bit(n);
bit.range_add(1, n, 1);
int ans = 0;
for (int i = 1;i <= n;i++) {
int p = pos[i], t = bit.get(p);
auto &from = (t ? s2 : s1), &to = (t ? s1 : s2);
while (1) {
auto [l, r] = from.back();
if (l <= p and p <= r) break;
ans += r - l + 1;
bit.range_add(l, r, t ? -1 : 1);
to.push_back({l, r});
from.pop_back();
}
auto [l, r] = from.back();
if (t) {
ans += p - l + 1;
if (l <= p - 1) {
bit.range_add(l, p - 1, -1);
to.push_back({l, p - 1});
}
if (p + 1 <= r) from.back().first = p + 1;
else from.pop_back();
}
else {
ans += r - p + 1;
if (p + 1 <= r) {
bit.range_add(p + 1, r, 1);
to.push_back({p + 1, r});
}
if (l <= p - 1) from.back().second = p - 1;
else from.pop_back();
}
}
cout << ans;
}
載入留言中…