Codeforces Round #541 (Div. 2) G dp + 思维 + 单调栈 or 链表 (连锁反应)

时间:2024-01-16 11:22:44

https://codeforces.com/contest/1131/problem/G

题意

给你一排m个的骨牌(m<=1e7),每块之间相距1,每块高h[i],推倒代价c[i],假如\(abs(i-j)<h[i]\),那么向j方向推倒i,j也会倒,问选择任意数量骨牌向任意方向推到,使得全部骨牌都倒下的代价最小

题解

  • 连锁反应可以用单调栈或者链表模拟
  • 定义dp[i]为推倒a[i,m]的最小代价
  • 对于每个i,有两种选择:
    • 向左推:\(dp[l[i]+1]=min(dp[l[i]+1],dp[i+1]+c[i])\)
    • 向右推:\(dp[i]=min(dp[i],rf[i]+c[i]),rf[i]\),\(rf[i]\)为推倒i能到达的位置上最小dp值
  • 单调栈写法很难懂

代码

链表写法
#include<bits/stdc++.h>
#define ll long long
#define mxN 300005
#define mxM 10000005
#define inf 0x3f3f3f3f
using namespace std;
ll n,m,i,j,k,N,q,x,y,p;
int l[mxM],h[mxM],r[mxM];
vector<array<int,2>>a[mxN];
ll rf[mxM],f[mxM],c[mxM]; int main(){
cin>>n>>m;
for(i=0;i<n;i++){
scanf("%lld",&N);
a[i].resize(N);
for(j=0;j<2;j++)
for(k=0;k<N;k++)
scanf("%d",&a[i][k][j]);
}
cin>>q;
for(i=0;i<q;i++){
scanf("%lld%lld",&x,&y);
for(j=0;j<a[x-1].size();j++,p++){
h[p]=a[x-1][j][0];
c[p]=a[x-1][j][1]*y;
l[p]=p-1;
while(l[p]>=0&&p-l[p]<h[p])
l[p]=l[l[p]];
}
}
memset(f,inf,sizeof(f));
f[m]=0;
for(i=m-1;i>=0;i--){
rf[i]=f[i+1];
r[i]=i+1;
while(r[i]<m&&r[i]-i<h[i]){
rf[i]=min(rf[r[i]],rf[i]);
r[i]=r[r[i]];
}
f[l[i]+1]=min(f[l[i]+1],f[i+1]+c[i]);
f[i]=min(f[i],rf[i]+c[i]);
}
cout<<f[0];
}

单调栈写法

#include<bits/stdc++.h>
#define ll long long
#define mxN 300005
#define mxM 10000005
#define inf 0x3f3f3f3f
using namespace std;
ll n,m,i,j,k,N,q,x,y,p,l,r;
int h[mxM],cnt[mxM];
vector<array<int,2>>a[mxN];
ll rf[mxM],f[mxM],c[mxM],val; int main(){
cin>>n>>m;
for(i=0;i<n;i++){
scanf("%lld",&N);
a[i].resize(N);
for(j=0;j<2;j++)
for(k=0;k<N;k++)
scanf("%d",&a[i][k][j]);
}
cin>>q;
for(i=0;i<q;i++){
scanf("%lld%lld",&x,&y);
for(j=0;j<a[x-1].size();j++){
h[++p]=a[x-1][j][0];
c[p]=a[x-1][j][1]*y;
}
}
stack<array<ll,2>>s1;
stack<ll>s2;
s1.push({m+1,0});
s2.push(1e17);
//memset(f,inf,sizeof(f));
for(i=m;i>=1;i--){
r=min(m,i+h[i]-1);
while(r>=s1.top()[0])s1.pop();
cnt[s1.top()[0]-1]++;
s1.push({i,0});
}
while(!s1.empty())s1.pop();
s1.push({0,0});
for(i=1;i<=m;i++){
l=max(1ll,i-h[i]+1);
val=f[i-1];
while(l<=s1.top()[0]){
val=min(s1.top()[1],val);
s1.pop();
}
s1.push({i,val});
s2.push(min(s2.top(),f[i-1]+c[i]));
f[i]=min(s2.top(),val+c[i]);
for(j=0;j<cnt[i];j++)s2.pop();
}
cout<<f[m];
}