CF1523F Favorite Game | Arahc's Home

题面

简化题意

有 $n$ 个传送门，初始都没有激活，有 $m$ 个任务。一个任务要求在 $t_i$ 时刻恰好处在 $(x_i,y_i)$ 的位置。如果你到了一个传送门你就可以激活它。任意时刻你可以从任意位置传送到一个已激活的传送门的位置。每个时刻你可以不动或者往上下左右某个方向走一步。

求最多能完成多少任务。

$n\leq14,m\leq100$ 。

题解

为了方便，将一个传送门位置或者任务点位置统称为『关键点』。并将所有任务按 $t$ 排序。

不难想到一个暴力 DP： $f_{s,j,k}$ 表示当前激活的传送门集合是 $s$ ，当前在第 $j$ 个关键点，已经完成了 $k$ 个任务需要的最小时间。

状态数就有 $m2^n(n+m)$ 了，不能通过。

考虑把状态拆成两个，分别转移。

设 $f$ 表示传送门位置， $g$ 表示任务点位置。注意到如果你在传送门，因为传送门之间可以随意传送，所以你在哪个传送门是不关心的；如果你在任务点，因为任务要求你需要在时刻 $t$ 在这里，所以时间是固定的。

因此设 $f_{s,i}$ 表示激活的传送门集合为 $s$ ，完成了 $i$ 个任务，在某个传送门的最小时间； $g_{s,i}$ 表示激活的传送门集合为 $s$ ，在第 $i$ 个任务点，最多能完成多少任务。

转移分传送门到传送门、传送门到任务点、任务点到传送门、任务点到任务点四种方案转移。复杂度为 $2^nm^2$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=15,max_m=102,inf=1000000009;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m,S;
int f[1<<14][max_m],g[1<<14][max_m];

struct Key{
    int x,y,t;
    Key(){t=0;}
    bool operator < (const Key &b) const{
        Key a=*this;
        return a.t<b.t;
    }
}a[max_n],b[max_m];

inline int Dis(Key a,Key b){
    return abs(b.y-a.y)+abs(b.x-a.x);
}

int ptt[1<<14][max_m],ptp[1<<14][max_n];

signed main(){
    n=read(),m=read(),S=(1<<n);
    memset(f,0x3f,sizeof(f)),memset(g,0xaf,sizeof(g));
    memset(ptt,0x3f,sizeof(ptt)),memset(ptp,0x3f,sizeof(ptp));

    for(register int i=0;i<n;++i)
        a[i].x=read(),a[i].y=read();
    for(register int i=1;i<=m;++i)
        b[i].x=read(),b[i].y=read(),b[i].t=read();
    sort(b+1,b+1+m);

    for(register int s=0;s<S;++s)
        for(register int i=0;i<n;++i) if((s>>i)&1){
            for(register int j=1;j<=m;++j)
                ptt[s][j]=min(ptt[s][j],Dis(a[i],b[j]));
            for(register int j=0;j<n;++j)
                ptp[s][j]=min(ptp[s][j],Dis(a[i],a[j]));
        }
    for(register int i=0;i<n;++i)
        f[1<<i][0]=0;
    for(register int i=1;i<=m;++i)
        g[0][i]=1;
    for(register int s=0;s<S;++s){
        for(register int i=0;i<=m;++i){
            if(f[s][i]>inf) continue;
            for(register int j=1;j<=m;++j)
                if(f[s][i]+ptt[s][j]<=b[j].t)
                    g[s][j]=max(g[s][j],i+1);
            for(register int j=0;j<n;++j)
                if(!((s>>j)&1))
                    f[s|(1<<j)][i]=min(f[s|(1<<j)][i],f[s][i]+ptp[s][j]);
        }
        for(register int i=1;i<=m;++i){
            if(g[s][i]<-inf) continue;
            for(register int j=i+1;j<=m;++j)
                if(b[i].t+min(Dis(b[i],b[j]),ptt[s][j])<=b[j].t)
                    g[s][j]=max(g[s][j],g[s][i]+1);
            for(register int j=0;j<n;++j)
                f[s|(1<<j)][g[s][i]]=min(f[s|(1<<j)][g[s][i]],b[i].t+min(Dis(b[i],a[j]),ptp[s][j]));
        }
    }
    int ans=0;
    for(register int s=0;s<S;++s)
        for(register int j=1;j<=m;++j)
            ans=max(ans,g[s][j]);
    write(ans);
    return 0;
}