文章目录

• 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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。