鏈接：http://codeforces.com/contest/1380/problem/D

題目大意：

? ? ? ?n個士兵站成一排，每個有一個能力值a[i]（兩兩不同）。

? ? ? ?現在有兩種操作

? ? ? ? 1. 花費x的代價，擊敗連續的k個士兵。

? ? ? ? 2. 花費y的代價，選擇兩個相鄰的，大的擊敗小的。

? ? ? ?問留下所給的另外一個序列b的士兵，最小代價。

題目思路：

? ? ? ?明顯是根據b序列把各個a序列區間按照分開，然后把這些段兒刪掉即可，如果思考dp的話，明顯這是個和區間有關系，但是不太好轉移。

? ? ? ? 先考慮-1的情況吧，第一種就是b和a序列中的各個元素的先后順序不能發生變化。

? ? ? ? ? ? ? 第二種就是，當這一段長度不足k，而且段中的最大值，比這一段兩邊的還要大的時候，發現這個最大的怎么都刪不掉。

? ? ? ? 這時思路就出來了，只要按照夠不夠k個，最大元素和兩邊元素的大小關系就可以判斷了。

1。 當這一段不足k，且最大元素比兩邊的還要大，這個最大元素刪不掉，輸出-1.

2.? ? 當這一段不足k，最大元素比兩邊某個小，那么可以選擇一個一個刪。

3.? ? ?當這一段大于k個，那么無論如何都可以刪掉這一段，因為可以內部刪，在判斷k*y 和 x的關系，決定使用哪種刪法貪心，前? ? ? ? ?提是要先把%k的余數那一部分處理掉，再解決這個剩下的k的倍數。

? ? ? ?代碼中再a，b序列的首位添加了-1便于操作，雙指針的方法，idx1，idx2是指在a上滑動，定位待刪除區間。idx3是在b上滑動，表示現在要在a中定位的兩個值。

#include<bits/stdc++.h> #define ll long long using namespace std; const ll MAXN = 2e5+5; ll b[MAXN],a[MAXN]; int main() {ll n,m;ll x,k,y;cin>>n>>m;cin>>x>>k>>y;a[0] = b[0] = -1;for(ll i=1;i<=n;i++){cin>>a[i];}for(ll i=1;i<=m;i++){cin>>b[i];}a[++n] = -1;b[++m] = -1;ll idx1 = 0;ll idx2 = 0;ll idx3 = 0;ll ans = 0;bool f = 1;while(idx3<m){while(idx1<=n){if(a[idx1]!=b[idx3]){idx1++;}else{break;}}if(idx1>n){f=0;break;}idx3++;while(idx2<=n){if(a[idx2]!=b[idx3]){idx2++;}else{break;}}// cout<<idx1<<" * "<<idx2<<" * "<<idx3<<endl;if(idx2>n){f = 0;break;}ll num = idx2-idx1-1;ll Max = 0;for(ll i=idx1+1;i<=idx2-1;i++){Max = max(Max,a[i]);}// cout<<Max<<" ** "<<endl;if(num<k){if(Max<a[idx1] || Max<a[idx2]){ans += num*y;// cout<<num*y<<" ****1 "<<endl;}else{f=0;break;}}else{ll md = num%k;ll cnt = num/k;num -= md;ans += md*y;// cout<<md*y<<" ***+ "<<endl;if(y*k<x){if(Max<a[idx1] || Max<a[idx2]){ans += y*num;}else{ans += x;ans += (num-k)*y;}// cout<<num*y<<" ****2 "<<endl;}else{ans += cnt*x;// cout<<cnt*x<<" ****3 "<<endl;}}//cout<<endl;}if(!f){cout<<-1<<endl;}else {cout<<ans<<endl;} }

?

總結

以上是生活随笔為你收集整理的Codeforces D. Berserk And Fireball（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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