題目鏈接

https://codeforces.ml/contest/1380/problem/D

前天的cf 到現在才a 我好菜啊 菜雞爆哭
又是一場unrated 這兩天cf測評機炸一場，網站炸一場
就不讓人打唄 像掉分都不讓

題目思路

題目給出兩個數組a，b
給出兩種方式將a變成b
第一種是直接將連續的區間長度為k的區間清除 費用為k
第二種是選取兩個連續的數 清除小的那個
求把a變成b的最小消費
如果無法將a變成b
則輸出-1

這題就直接模擬就好了
但是寫不來模擬的我真是寫到想死 說到底還是題做少了
首先先判斷b上的數大致位置是否和a中一樣
如果一樣再繼續
遍歷所有區間
對于不同的區間長度 大體可以分成兩類
小于k 和大于等于k的

如果小于k時 只能用第二種方法
但如果此區間中最大值大于區間最近的左值和右值的話
這個區間是無法完全清除的
所以需要記錄區間最大值 判斷這種情況
如果可以請除 那么這一區間的話費是len*y

當區間長度大于等于k時
兩種方法都能做
就先按照比較一二兩種方式誰更劃算
即比較x和k*y的值
小于等于的話只用第一種方法就好了
花費為len/k+x
大于的話在判斷如果此區間是無法完全用第二種方法清除的話（見上一種情況）
我們先就先用第一種方式消去包含最大值的區間 再用第二種就好了
花費為（len-k） * y+x
否則直接用第二種方式清除即可
花費為len * y
還有就是在比較之前可以先將長度除以k的余數用第二種方式清除
具體細節見代碼和注釋

ac代碼

#include <stdio.h> #include <iostream> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <utility> #define pi 3.1415926535898 #define ll long long #define lson rt<<1 #define rson rt<<1|1 #define eps 1e-6 #define ms(a,b) memset(a,b,sizeof(a)) #define legal(a,b) a&b #define print1 printf("111\n") using namespace std; const int maxn = 2e5+10; const int inf = 0x1f1f1f1f; const int mod = 2333;ll a[maxn],pos[maxn],b[maxn];int main() {//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);int n,m;scanf("%d%d",&n,&m);ll x,k,y;scanf("%lld%lld%lld",&x,&k,&y);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);pos[a[i]]=i;//將a數組中的值的位置記錄下來 方便之后的判斷和找區間}a[n+1]=-inf;//這里是當做最后一個區間的右端點 之前寫的inf 一直wa 后來發現這樣會影響到后面判斷區間是否能完全清除 改成了-inf就過了for(ll i=1;i<=m;i++){scanf("%lld",&b[i]);}ll flag=0;for(ll i=1;i<m;i++){if(pos[b[i]]>pos[b[i+1]])flag=1;}if(flag==1)printf("-1\n");else{ll l=0,r=0;ll ans=0;for(ll i=1;i<=m+1;i++){if(i==m+1)r=n+1;elser=pos[b[i]];if(r-l-1>0)//判斷這一段是否有區間需要被消除{ll maxx=0;for(ll j=l+1;j<=r-1;j++){maxx=max(a[j],maxx);}if(maxx<a[l]|maxx<a[r])//判斷區間能否被完全清除flag=0;elseflag=1;if(r-l-1<k){if(flag==1){printf("-1\n");return 0;}elseans+=(r-l-1)*y;}else{ll len=r-l-1;ll tem=len%k;ans+=tem*y;len-=tem;if(x<=k*y){ans+=len/k*x;}else if(flag){ans+=(len-k)*y+x;}else{ans+=len*y;}flag=0;}}l=r;}printf("%lld\n",ans);} }

這種模擬還是挺考驗碼力的 有些細節寫搓了就會wa到死 還很難發現
還是要多刷題 碼力不夠

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 91 (Rated for Div. 2) . d Berserk And Fireball的全部內容，希望文章能夠幫你解決所遇到的問題。

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