Codeforces D. Berserk And Fireball（贪心）

链接：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;
    }
}