e686 - 11908 - Skyscraper
題目描述
題目要求在建築物外牆上放置廣告，每個廣告訂單有最低樓層、覆蓋樓層數和收益。目標是選擇廣告訂單，使得沒有樓層被重複覆蓋，並最大化總收益。
解題思路
本題可以使用動態規劃來解決。首先，將廣告訂單按照最低樓層排序。然後，使用 DP[i] 表示考慮前 i 個廣告訂單時可以獲得的最大收益。對於每個廣告訂單，我們有兩種選擇：接受或拒絕。如果接受該訂單，則需要確保其覆蓋的樓層沒有被之前的訂單覆蓋。可以使用二分搜尋找到上一個不與當前訂單衝突的訂單，並更新 DP[i] 的值。如果拒絕該訂單，則 DP[i] 的值與 DP[i-1] 相同。最終，DP[n] 就是可以獲得的最大收益。
複雜度分析
- 時間複雜度: O(n log n) (排序需要 O(n log n)，二分搜尋在迴圈中需要 O(log n)，迴圈執行 n 次，所以總體是 O(n log n))
- 空間複雜度: O(n) (DP 陣列需要 O(n) 空間)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int t,n,rw[30005];
pair <int,pair <int,int> > a[30005];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> n;
int DP[30005]={0};
for(int i=1;i<=n;++i){
cin >> a[i].second.first >> a[i].first >> a[i].second.second;
a[i].first+=a[i].second.first;
}
sort(a+1,a+n+1);
for(int i=0;i<=n;++i)rw[i]=a[i].first;
for(int i=1;i<=n;++i)
DP[i]=max(DP[i-1],DP[upper_bound(rw,rw+i,a[i].second.first)-rw-1]+a[i].second.second);
cout << "Case " << ca << ": " << DP[n] << '\n';
}
}