codeforces1396C

(Updated: )
(3 mins to read)

有n个关卡，每关有$a_i$​个小怪(1hp)和1个boss(2hp)，在第i关可以转移到i-1和i+1关，需要花费d，有三种武器

  • 花费r1，让一只怪物-1hp
  • 花费r2，让所有怪物-1hp
  • 花费r3，秒杀一只怪物

其中第一和第三种武器必须在没有小怪的情况下才能攻击boss，并且如果没有秒掉boss（还剩1滴血），则会被强制转移到相邻的关卡（花费d），问你杀死所有怪物的最小花费$n \leq 10^6,1\leq r1 \leq r2 \leq r3 \leq 10^9$

解法

在某一关中我们要么用r3直接秒掉boss避免强制转移(先用r1清小怪)，要么就先让boss少一滴血(用r1清小怪再点一下boss或者一下r2)转移走，之后再回来用一下r1点死boss。所以每关其实只有两种选择，一是用r1杀掉小怪后用r3秒掉boss(cost1=a[i]*r1+r3)，二是用r2或者(a[i]*r1+r1)让boss剩1hp然后强制转移走回来后再花r1杀死boss(cost2=min(a[i]*r1+r1,r2))，然后就可以dp了$dp_{i,0}$​表示第i关已经解决的最小费用，$dp_{i,1}$​表示第i关的boss还剩1hp然后还没强制跳转的最小费用$dp_{0,0}=min(dp_{i-1,0}+d+min(cost1,2*d+cost2+r1),dp_{i-1,1}+3*d+r1+min(cost1,cost2+r1))$如果上一关已经消灭($dp_{i-1,0}$​)，这一关要么就cost1，要么就cost2然后来回跳两个d，再一个r1补死如果上一关还有1hp，那么这关消灭后再回去补死上一关再回来$dp_{i,1} = dp_{i-1,0}+d+cost2$还有一种特殊情况就是在倒数第二关强制转移到最后一关，然后消灭最后一关再转移到倒数第二关补死之后结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int n, a[N];
ll r1, r2, r3, d, dp[N][2];
int main()
{
  scanf("%d%lld%lld%lld%lld", &n, &r1, &r2, &r3, &d);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = -d;
  for(int i=1; i<=n; i++)
  {
    ll c1 = min(a[i]*r1+r1, r2), c2 = a[i]*r1 + r3;
    dp[i][0] = min(dp[i-1][0]+d+min(c2, 2*d+c1+r1), dp[i-1][1]+3*d+r1+min(r1+c1, c2));
    dp[i][1] = dp[i-1][0]+d+c1;
  }
  ll ans = min(dp[n][0], dp[n-2][0]+d+a[n]*r1+r3+r1+2*d+min(a[n-1]*r1+r1, r2));
  printf("%lld\n", ans);
  return 0;
}