P4766 [CERC2014] Outer space invaders

· · 题解

P4766 [CERC2014] Outer space invaders

一道经典的区间dp，但之前没见过这种套路，有点不知所措。

设状态时想到以d_i设会因为不方便考虑时间而无法转移，所以设f_{l,r}表示[a_i,b_i]\subseteq [l,r]的所有i被消灭的最小花费。

一开始想到把序列按某种方式排个序，然后枚举k表示在时间k放，但可以发现我们虽然知道这时候放影响到了哪些i，但无法确定我们放的距离，因为这些i可能在k以外的时间已经被处理掉了，我们不能将它的影响算入。但枚举k后再去排除左右区间最优解时被处理掉的i时间开销不起，也太复杂。

区间dp转移时，重点是要找到区间中某个开销及他所能满足的所有条件，然后从除去这些条件的两个子区间转移。

看了题解后，意识到我们如果有一个一定要花费的d，再枚举什么时候放这个炮就可以解了，注意到每个时间段内d_{max}是必须单独放一炮的，所以他就是我们所找的一定要花费的东西，之后方程就简单了：

f_{l,r}=\min\limits_{k\in[a_i,b_i]}(f_{l,k-1}+f_{k+1,r})+d_i 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=610;
ll f[N][N];
int t,n,a[N],b[N];
int ds[N],d[N],m;
int main(){
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&a[i],&b[i],&d[i]),
            ds[i]=a[i],ds[i+n]=b[i];
        sort(ds+1,ds+1+2*n);
        m=unique(ds+1,ds+1+2*n)-ds-1;
        for(int i=1;i<=n;i++)
            a[i]=lower_bound(ds+1,ds+1+m,a[i])-ds,
            b[i]=lower_bound(ds+1,ds+1+m,b[i])-ds;
        for(int i=1;i<=m;i++)
            for(int j=i;j<=m;j++)
                f[i][j]=1e18;
        for(int len=1;len<=m;len++)
        {
            for(int l=1;l+len-1<=m;l++)
            {
                int r=l+len-1;
                int mxd=0;
                for(int i=1;i<=n;i++)
                    if(a[i]>=l&&b[i]<=r&&d[i]>d[mxd])
                        mxd=i;
                if(!mxd){
                    f[l][r]=0;
                    continue;
                }
                // cout<<d[mxd]<<" "<<a[mxd]<<" "<<b[mxd]<<"\n";
                // cout<<f[l][r]<<"\n";
                for(int k=a[mxd];k<=b[mxd];k++)
                    f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+d[mxd]);
                // cout<<f[l][r]<<" "<<l<<" "<<r<<"\n";
            }
        }
        printf("%lld\n",f[1][m]);
    }
    return 0;
}