一道思维好题，写篇题解纪念一下。

Problem Description

有 \(n\) 个敌人，你需要在第 \(k_i\) 秒用至少 \(h_i\) 的攻击力打败这个敌人。

攻击力的计算方式如下：

  1. 第一秒时，你有 \(1\) 攻击力
  2. 对于后面的任意一秒，若前一秒你的攻击力为 \(x\)，则这一秒你的攻击力可以为 \(x+1\) 或 \(1\)

一秒内，如果你的攻击力为 \(x\)，则你就需要消耗 \(x\) 的能量。

请问，在你打败所有敌人的情况下，最少需要消耗多少能量。

题目分析

在一秒内，你可以继承之前的攻击力，但是继承攻击力的代价就是你要花费相当于继承之后攻击力的法力值来保存你的攻击力。只有当前攻击力大于当前出现的怪物的血量的时候，你才能杀死他。在任意一秒，你可以选择摆烂，但是摆烂的代价就是会丢失上一秒的攻击力，使你在下一秒的时候无法有之前那么高的攻击，摆烂可以选择从 \(0\) 开始或者从 \(1\) 开始。显然可以发现，当 \(k_i\ge h_i\) 的时候，主角总是有办法杀死所有的怪物的。

在杀死所有的怪物的怪物下要保证消耗的法力值最少，那就需要我们合理分配增加攻击的时间了。我们不难得出以下结论：

如果在第 \(k_i\) 秒遇到了血量为 \(h_i\) 的怪物，那么在 \((k_i-h_i,k_i]\) 的时间区间内，我不能出现摆烂的情况，即攻击力不能掉，在 \(k_i-h_i\) 的时刻，攻击力不能减为 \(0\)。

那么第 \(i\) 个怪物需要我花费的最少法力值就是从 \(1\) 到 \(h_i\) 的等差数列，假设我打完怪物之后我都能立刻摆烂，那么不难得出总法力消耗就是 \(\sum _{i=1}^{n} \sum _{j=1}^{h_i} j\) 。但是并不是每一次打完怪物我都能摆烂，如果我摆烂到 \(0\)，剩下的时间不足以我积攒足够的攻击去击杀接下来的怪物那就不能摆烂而是接着蓄力。

对于每一个怪物我们都构造一个区间，区间范围为 \([k_i-h_i+1,k_i]\) ，当区间出现相交，则合并两个区间，最后根据区间长度计算法力值即可。

对于每一个区间我观察我的左端点是否会落在上一个区间内，如果在，则需要合并前面的区间，因为我们默认按照 \(k_i\) 排序了，也就是按照区间右端点值排序，所以我可以用 \(\text{lower\_bound}\) 来寻找合并的区间。因为如果最后一个怪物它要求我从第一秒开始蓄力的话，那么前面的所有区间我都要合并，所以这里必须考虑合并的区间。对于合并的区间我们修改 \(l\) 为其中最小值，\(r\) 为其中最大值。然后在计算区间的时候特判一下连续的区间是否相等，达到只计算一次的目的即可。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define maxn 105
using namespace std;
int h[maxn],k[maxn],l[maxn],r[maxn];
void solve(){
    int n;
    cin>>n;
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(l));
    for(int i=1;i<=n;i++)cin>>k[i];
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++){
        l[i]=k[i]-h[i]+1;
        r[i]=k[i];
    }
    
    for(int i=1;i<=n;i++){
        if(l[i]<=r[i-1]){
            int j=i;
            int p=lower_bound(r+1,r+1+i,l[i])-r;
            //if(p==0)p++;
            for(int j=p;j<=i;j++){
                l[j]=min(l[p],l[i]);
                r[j]=r[i];
            }
        }
    }


    long long ans=0;
    for(int i=1;i<=n;i++){
        if(l[i]==l[i-1]&&r[i]==r[i-1])continue;
        int num=r[i]-l[i]+1;
        ans+=1ll*(num+1)*num/2;
        if(l[i]-r[i-1]>1&&l[i-1]!=0){
            ;//ans+=l[i]-r[i-1]-1;
        }
    }
    cout<<ans<<endl;
}

int main(){
    //freopen("1.in","r",stdin);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}