CF1396C Monster Invaders 题解

· · 题解

首先需要正确理解题面：

  1. 手枪、激光枪、AWP 分别有 r1,r2,r3 的冷却时间，但是这个冷却实际上是蓄力前摇，不能同时冷却。

  2. 这些枪都不不能打其他关卡的怪。

首先分析下三个武器：

  1. 手枪：相当于每次杀死一个小怪。打 boss 时会先打一枪，然后被送走，后来后再打一枪。

  2. 激光枪：相当于杀死关卡中所有小怪，打掉 boss 一滴血，然后被送走。显然一关最多在开头使用一次激光枪。

  3. AWP：直接杀死一个怪。

分析一下打过某一关的方式：

  1. 开头使用一次激光枪，然后被送走，回来用一次手枪打死 boss。

  2. 使用手枪打完小怪，打 boss 一枪，然后被送走，后来后再打一次手枪。

  3. 使用手枪打完小怪，然后使用 AWP 杀死 boss。

考虑前两个方式，我们称为打法一，第三个方式称为打法二，对于打法一的连续段：

  1. 连续段在中间，那么连续段中相邻两关的路程会贡献 3 次。

  2. 连续段在最后：那么最后一关使用打法二，然后回依次向前被送走，打完每个 boss。

于是设计一个 dp 状态：

分类讨论一下转移即可，特别的当 dp_{n,2} 的代价是直接击杀 boss 的代价。看代码就能看懂这个分类讨论了。

#include<bits/stdc++.h>

int read(){
    int x;
    scanf("%d",&x);
    return x;
}

void print(long long x){
    printf("%lld",x);
    return;
}

long long arr[1000010],dp[1000010][3];

int main(){
    register int i;
    long long r1,r2,r3,d,val1,val2;
    int n=read();
    r1=read();
    r2=read();
    r3=read();
    d=read();

    dp[0][0]=-d;

    for(i=1;i<=n;++i){
        arr[i]=read();
        val1=r1*arr[i]+r3;
        val2=std::min(r1*arr[i]+r1,r2)+r1;

        dp[i][0]=std::min({
            dp[i-1][0]+val1+d,
            dp[i-1][1]+val1+d+d*2,
            dp[i-1][0]+val2+d+d*2,
            dp[i-1][1]+val2+d+d*2,
        });
        dp[i][1]=std::min({
            dp[i-1][0]+val1+d,
            dp[i-1][1]+val1+d+d*2,
            dp[i-1][0]+val2+d,
            dp[i-1][1]+val2+d+d*2,
        });
        if(i==n) val2=std::min(val2+d*2,val1);
        dp[i][2]=std::min({
            dp[i-1][2]+val2+d+d,
            dp[i-1][0]+val2+d,
            dp[i-1][1]+val2+d+d*2,
        }); 

    }

    print(std::min(dp[n][0],dp[n][2])); 

    return 0;
}