Monsters And Spells

题目来源：C - Monsters And Spells (codeforces.com)

题目：

输入输出及样例：

解题思路：

这道题 t 的范围 10的4次方，n 的范围是100， 猜测应该在(O(n)) 的复杂度内解决。

题目可以等价地这样抽象：

在一条表示时间的坐标轴上，相对应有一系列整数点（怪兽）。我们需要在轴上画一系列不重叠的线段（端点整数），线段左端点标记为1，接下来各整数点依次标记2，3，4等等。要求我们的线段覆盖怪兽点，并且覆盖点的标记值要比怪兽的值大（或相等）。最终使标记的和尽量小。

此题可以倒着进行考虑，从最后一条线段到第一条，逐个确定。

首先找到最后一个怪兽点，作为最后一条线段的右端点，然后根据这个怪兽的值，得出这条线段的左端点的位置。如果确定出的这条线段没有跨越前一个点，则这条线段可以确定下来了，加到答案中。如果这条线段（线段1）跨越了前一个点，那么再以前一个点为 线段2 的右端点，得出 线段2 的左端点，比较2 的左端点和 线段1 的左端点，取更左边的点作为 合并线段 的左端点，取 线段1 的右端点作为合并线段的右端点，再看这条 合并线段 有没有跨越再往前一个点，以此类推。

直到所有线段都被确定下来，即可得出最终答案，详见注释。

AC代码：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 108;
int n;
ll ans;
pair<ll,ll> p[maxn];

#define sum(i,j) (i==j?i:(j-(i)+1ll)*(i+j)/2ll)

signed main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans = 0;
        for(int i=1;i<=n;++i)
            scanf("%lld",&p[i].first);   
        for(int i=1;i<=n;++i)
            scanf("%lld",&p[i].second);
        int pn = n;     //当前被覆盖的怪兽点
        ll rig,lef;     //当前合并线段的右端点和左端点
        while(pn>=1)
        {
            rig = p[pn].first;   //更新右端点
            lef = p[pn].first - p[pn].second + 1;  //更新左端点
            while(lef<=p[pn-1].first)   //判断是否覆盖前一个点
            {
                pn--;
                lef = min(lef,p[pn].first-p[pn].second+1);  //更新左端点
            }
            ans += sum(1,rig-lef+1);   //加上这条线段
            pn--;
        }
        printf("%lldn",ans);
    }

	return 0;
}

自己犯的错误：

1. 一开始宏定义写成了 #define sum(i,j) (i==j?i:(j-i+1ll)*(i+j)/2ll)不加括号，活该不对。

2. 一开始考虑不周，不是倒着写的而是正着写的。结果出现了中间某个点本该一直增大法力值但是却从1开始，导致后面某个点无法消灭怪兽的问题。仔细来想，实质上因为正着画线段，当前解对于后面的解是有影响的。但是倒着画线段，一旦画出一条线段，剩下的子问题完全独立，不受已经解决的问题的影响，所以就行了。