problem

LOJ2772

solution

這道題求的是“保證最多”，這個“保證”真的屑啊！

因為我們無法確定實驗生成的克數，所以我們應當計算的是最壞情況。

又因為我們可以選擇做哪些實驗，所以要的是所有實驗組合最壞情況下的最大價值。

如果題目讀錯成直接求最多，那么就會寫出線段樹優化 $dp$，結果樣例都過不了！！

---

將答案數學化長相表示出來，設 $d{p}_i:$ 已經裝了 $i$ 克反物質，最大保證還能獲得多少價值。

轉移有，$d{p}_i={\max }_{1\le j\le n}\{{\min }_{l_j\le k\le r_j}\{d{p}_{i+k}+1e9?k?c_j\}\}$。答案即為 $d{p}_0$。

其實只要搞清楚這一點，列出這個轉移，剩下的優化部分已經是非常簡單的了。

$k\in [l_j,r_j]\to i+k\in [i+l_j,i+r_j]$，這濃濃的滑動窗口味兒。

稍微改寫一下，初始化 $d{p}_i=1e9?i$，$d{p}_i={\max }_{1\le j\le n}\{{\min }_{l_j\le k\le r_j}\{d{p}_{i+k}\}?c_j\}$。

然后對每個實驗都開一個維護遞增的單調隊列，用隊首更新答案。

$i??$，彈出單調隊列中不在 $[i+l_j,i+r_j]$ 的元素，每次都要新加 $i+l_j$。

這些都是套路，時間復雜度 $O(na)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 105 #define maxv 2000005 #define int long long const int NB = 1e9; int n, a; int l[maxn], r[maxn], c[maxn]; int f[maxv << 1]; deque < pair < int, int > > q[maxn];signed main() {scanf( "%lld %lld", &n, &a );for( int i = 1;i <= n;i ++ ) scanf( "%lld %lld %lld", &l[i], &r[i], &c[i] );for( int i = a + 1;i <= (a << 1);i ++ ) f[i] = -1e18; //將爆出實驗的設為極小值 就不會被誤判為答案for( int i = a;~ i;i -- ) {f[i] = NB * i;for( int j = 1;j <= n;j ++ ) {//[i+l(j),i+r(j)] 才會對i產生貢獻 且是這段里的最小值貢獻//i+l(j) 在i+1容量中沒有被計入 這里計入while( ! q[j].empty() and q[j].back().second >= f[i + l[j]] ) q[j].pop_back(); //維護單增隊列q[j].push_back( make_pair( i + l[j], f[i + l[j]] ) );while( ! q[j].empty() and q[j].front().first > i + r[j] ) q[j].pop_front(); //彈出不在范圍內的f[i] = max( f[i], q[j].front().second - c[j] ); //實驗是可以選的 所以外層dp比較取較大值}}printf( "%lld\n", f[0] );return 0; }

總結

以上是生活随笔為你收集整理的「ROI 2017 Day 2」反物质（单调队列优化dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。