php商城网站建设,js wordpress 菜单管理系统,网站设计模板源码,深圳企业网站建设设计文章目录problemsolutioncodeproblem
solution dpi:dp_i:dpi: 前iii个多米诺骨牌全都倒下的最小花费 li,ril_i,r_ili,ri分别表示第iii个多米诺骨牌倒下时所能波及到的最左/右位置 往左倒#xff0c;则[li,i)[l_i,i)[li,i)内的牌都可以选择性地先推倒 dpimin{dpjcos…
文章目录problemsolutioncodeproblem
solution
dpi:dp_i:dpi: 前iii个多米诺骨牌全都倒下的最小花费
li,ril_i,r_ili,ri分别表示第iii个多米诺骨牌倒下时所能波及到的最左/右位置 往左倒则[li,i)[l_i,i)[li,i)内的牌都可以选择性地先推倒 dpimin{dpjcosti∣li−1≤ji}dp_i\min\{dp_jcost_i\big|l_i-1\le ji\}dpimin{dpjcosti∣∣li−1≤ji} 被后面的牌左倒后推倒 dpimin{dpj−1costj∣ji≤rj}dp_i\min\{dp_{j-1}cost_j\big|ji\le r_j\}dpimin{dpj−1costj∣∣ji≤rj}
性质相邻两多米诺骨牌的波及范围只有包含或相离关系
显然若iii能波及jjj则jjj能波及范围一定能被iii波及到
两种情况都可以用单调栈优化求解O(m)O(m)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;
}
