[CERC2014] Outer space invaders

题目描述

The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated!

Or assimilated. Or eaten. We are not yet sure.

The aliens follow a known attack pattern. There are nn attackers, the i−thi−th one appears at time aiai​, at distance didi​ from you. He must be destroyed no later than at time bibi​, or else he will fire his weapon, which will definitely end the fight.

Your weapon is an area-blaster, which can be set to any given power. If fired with power RR,it momentarily destroys all aliens at distance RR or smaller. It also consumes RR fuel cells.

Determine the minimal cost (measured in fuel cells) of destroying all the aliens, without being killed.

输入格式

The first line of input contains the number of test cases TT. The descriptions of the test cases follow:

Each test case starts with a line containing the number of aliens n(1≤n≤300)n(1≤n≤300). Of the next nn lines, the i−thi−th one contains three integers ai,bi,di,(1≤ai<bi≤10000,1≤di≤10000)ai​,bi​,di​,(1≤ai​<bi​≤10000,1≤di​≤10000).

The i−thi−th alien appears at time aiai​, is idle until bibi​, and his distance from you is didi​.

输出格式

For each test case, output one line containing the minimum number of cells needed to destroy all the aliens.

题意翻译

题目描述

来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。

外星人遵循已知的攻击模式。有 NN 个外星人进攻，第 ii 个进攻的外星人会在时间 aiai​ 出现，距离你的距离为 didi​，它必须在时间 bibi​ 前被消灭，否则被消灭的会是你。

你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 RR，它会瞬间摧毁与你的距离在 RR 以内的所有外星人（可以等于），同时它也会消耗 RR 单位的燃料电池。

求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

输入格式

第一行输入一个数 TT,表示有 TT 组数据。

每组数据的第一行为外星人的数量 nn（1≤n≤3001≤n≤300）。

接下来 nn 行，每行有三个数 ai,bi,diai​,bi​,di​，表示这个外星人在时间 aiai​ 出现，距离你 didi​，在 bibi​ 前时刻死亡。

输出格式

共 TT 行，每行输出摧毁所有外星人的最低成本。

输入输出样例

1
3
1 4 4
4 7 5
3 4 7

7

和我上篇博客里面讲的dp是一种
先讲讲怎么做，再分析一下这类题目的特点和套路吧

首先看到这题目，就很明显是一个dp
线性的dp是很明显完全不可以的，没有特殊处理的状态是完全处理不了这种区间操作的后效性的

还是之前所说的，dp状态的设计要使在这个状态上的情况能够相互比较来选择出现在优秀，并且之后也优秀的情况
我们要设计一种状态，让不同情况在满足某些要求的时候能够公平的相互比较

（我念叨这些其实是因为我不知道怎么样来解释怎么想到这种状态设计。。。
等等。。我理清一下思路

首先，这题的一个麻烦之处在于，我们只是有一个时间区间的限制，我们只需要在这个区间内将其解决就好
可以很轻松的想到，每一次的击杀操作应该都是一个决策点
或者说是，我们的每一次击杀操作都是决策得到的

那我们转移的时候肯定是有一重循环在枚举什么时候击杀吧
我们发现我们的后效性是在时间维度上的，那我们就以时间维度来进行区间dp，就能够解决这种后效性了
这其实更趋近是一种感觉。。我在没有看题解的时候，否定了线性dp之后就很自然的想到了区间dp。。。
因为写了一些题目之后，应该是能够认识到区间dp其实就是一种处理后效性的方法吧？
但是转移并不是普通的方法，这是区间dp的另一类，或者说是一种进阶

设f[i][j]表示解决了出现时间和结束时间都在[i,j]之中的敌人所消耗的最小的能量和
但是转移很明显不是枚举断点这么简单
对于一个满足i<=k<=j的k，f[i][k]+f[k+1][j]和f[i][j]之间的差距在于那些出现时间在k的左边，消灭时间在k的右边的敌人，消灭他们既没有被f[i][k]完成，也没有被f[k+1][j]完成
所以我们只需要在k点完成这个击杀操作就好了

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
讲的好烂好烂
我感觉我理解之后为什么讲不出来我的思考过程了啊啊啊啊啊啊啊啊啊
好烦好烦好烦
哭了

所以方程就是。。。
算了这个大佬讲的比我好一万倍https://www.cnblogs.com/luckyblock/p/17056671.html

难绷

我就分析一下这个题型吧（给我自己看的罢了

这个题目和我上一篇博客所讲的题目是同一种
他们和石子合并这种传统的区间dp所不一样的地方在于，传统的区间dp的增加代价的操作往往是和区间合并一起发生的
而这一题和上一题的区间合并却似乎是以“最后一次操作”作为区间合并的一种条件，最后一次操作其实就是区间合并的操作，我们所做的就是枚举这个最后的操作发生的位置，然后以这位置作为断点来合并区间，转移状态
这个最后一次操作，可以说是消除了这两个区间之间被划分为两个区间的原因，从而变为一个区间
这一题是这样，上一题也是这样
上一题中，我们寻找的是最优的解，所以在对一个区间的转移全部完成后，我们需要保证这个区间对于的dp数组里面存放的一定是最优秀的解，而我们寻找一个贡献最大的奶牛，吃掉中间的派的操作，其实就是维护了最优解
很容易的可以证明，在我们这样对这个区间操作后，这里最后存放的一定是最优解。所以这是一个正确的dp

这两道题目有什么共同点吗？

首先，我们发现，奶牛的吃派是一个区间的操作，而我们击杀敌人也是一个区间的操作，更巧的是，我们枚举的“最后的操作”，在上一题就是奶牛吃派，在这一题里面就是击杀敌人
很明显这不是巧合，这里引用一句在网上看到的dalao的话：区间DP的另一大套路就是：当我不好"拆分-合并"的时候，先考虑最后执行的操作，再用这个最后执行的操作把区间分成两部分，可以视作"合并-拆分"。
其实这两题里面的操作就是区间的合并-拆分，这很明显

我们之所以不好合并-拆分，就是因为在我们合并两个区间的时候，其实是有需要满足的条件的，但是之前的基础的区间dp并没有这种东西，所以在之前的我看来，这东西就是不可做的
但是，我们可以把决策的操作加入，也就是上面说的，先考虑最后执行的操作

那我们有没有什么办法来判断这种类型的题目呢？

好难受，这种题目的模型为什么我建不起来
好难受好难受
他们有什么特点？是什么特点使他们必须使用这种办法来求解？
我现在能看到的，就是他们和柿子合并不一样的，他们是真正的区间操作，而柿子合并则是一个区间合并
那只要是区间操作求最优解的题目就能够用这种做法吗？
第二题和第一题的区别其实很大
我们转移时“最后执行的操作”其实是一个能够覆盖整个区间的操作，我们的状态设计使这个操作的影响被限制，没有波及其他区域
这使得后效性被处理
柿子合并没有这种范围的影响

难道特点就是“波及一个给定范围的操作”？
似乎不够
还有
这种操作如果使嗷付出代价的和如果使获得奖励的
这似乎不一样
这两道题目就是不一样的
但是，有一个可以确定的，就是先考虑最后执行的操作

目前我能想到的只有这些了。。

头疼

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int T,c[601],f[601][601];
struct node
{
    int a,b,d;
}e[601];
bool mycmp(node a,node b)
{
    if(a.a==b.a)return a.b<b.b;
    return a.a<b.a;
}
int main()
{
    T=read();
    while(T--)
    {
        int n=read(),tot=0;
        map <int,int> m;
        memset(f,0,sizeof(f));
        memset(e,0,sizeof(e));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            e[i].a=read();e[i].b=read();e[i].d=read();
            c[i]=e[i].a;c[i+n]=e[i].b;
            m[c[i]]=0;m[c[i+n]]=0;
        }
        sort(c+1,c+1+n*2);
        for(int i=1;i<=n*2;i++)
        {
            if(m[c[i]]==0)
                m[c[i]]=++tot;
        }
        for(int i=1;i<=n;i++)
        {
            e[i].a=m[e[i].a],e[i].b=m[e[i].b];
        }
        sort(e+1,e+1+n,mycmp);
        for(int i=2;i<=tot;i++)
        {
            for(int j=1;i+j-1<=tot;j++)
            {
                int r=i+j-1,get=0,ans=-1;
                for(int k=1;k<=n;k++)
                {
                    if(e[k].b>r&&e[k].a>r)break;
                    if(e[k].a>=j&&e[k].b<=r)
                    {
                        if(ans<e[k].d)
                        {
                            ans=e[k].d;
                            get=k;
                        }
                    }
                }
                if(ans!=-1)
                {
                    f[j][r]=2147483647;
                    for(int k=e[get].a;k<=e[get].b;k++)
                    {
                        f[j][r]=min(f[j][r],f[j][k-1]+f[k+1][r]+e[get].d);
                    }
                }
                else 
                {
                    f[j][r]=0;
                }
            }
        }
        cout<<f[1][tot]<<endl;
    }
    return 0;
}