文章目錄

• • problem
  • solution
  • code

problem

solution

$d{p}_i:$ 前$i$個多米諾骨牌全都倒下的最小花費

$l_i,r_i$分別表示第$i$個多米諾骨牌倒下時所能波及到的最左/右位置

• 往左倒，則$[l_i,i)$內的牌都可以選擇性地先推倒

  $d{p}_i=\min \{d{p}_j+cos{t}_i|l_i?1\le j<i\}$

• 被后面的牌左倒后推倒

  $d{p}_i=\min \{d{p}_{j?1}+cos{t}_j|j<i\le r_j\}$

性質：相鄰兩多米諾骨牌的波及范圍只有包含或相離關系

顯然，若$i$能波及$j$，則$j$能波及范圍一定能被$i$波及到

兩種情況都可以用單調棧優化求解，$O(m)$

code

#include <stack> #include <cstdio> #include <vector> using namespace std; #define maxm 10000007 #define maxn 250005 #define int long long int n, m, Q; stack < int > st; vector < int > a[maxn], c[maxn]; int h[maxm], w[maxm], l[maxm], r[maxm], dp[maxm];signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1, k;i <= n;i ++ ) {scanf( "%lld", &k );a[i].resize( k );c[i].resize( k );for( int j = 0;j < k;j ++ )scanf( "%lld", &a[i][j] );for( int j = 0;j < k;j ++ )scanf( "%lld", &c[i][j] );}scanf( "%lld", &Q );int cnt = 0;while( Q -- ) {int id, mul;scanf( "%lld %lld", &id, &mul );for( int i = 0;i < a[id].size();i ++ )h[++ cnt] = a[id][i], w[cnt] = c[id][i] * mul;}for( int i = 1;i <= m;i ++ ) {while( ! st.empty() && h[st.top()] + st.top() <= i )r[st.top()] = i - 1, st.pop();st.push( i );}while( ! st.empty() ) r[st.top()] = m, st.pop();for( int i = m;i;i -- ) {while( ! st.empty() && st.top() - h[st.top()] >= i )l[st.top()] = i + 1, st.pop();st.push( i );}while( ! st.empty() ) l[st.top()] = 1, st.pop();//維護往右倒的最小花費單調棧for( int i = 1;i <= m;i ++ ) {dp[i] = w[i] + dp[l[i] - 1];while( ! st.empty() && r[st.top()] < i ) st.pop();if( ! st.empty() ) dp[i] = min( dp[i], w[st.top()] + dp[st.top() - 1] );if( st.empty() || w[i] + dp[i - 1] < w[st.top()] + dp[st.top() - 1] )st.push( i );}printf( "%lld\n", dp[m] );return 0; }

簡單地讓人不會

總結

以上是生活随笔為你收集整理的CF1131 G. Most Dangerous Shark（DP+单调栈优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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