Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P6622 【[省选联考 2020 A/B 卷] 信号传递】

posted on 2020-06-23 17:11:03 | under 题解 |

一道奇特的状压dp。

分享一个$O(m^22^{m/2+1}+m2^m)$的做法。

首先m<=23,考虑做状压dp。

对于x前往y:

  1. x在左侧,提供$-p_x$的代价,在右侧,提供$p_x*k$的代价。

  2. y在左侧,提供$p_y*k$的代价,在右侧,提供$p_y$代价。

可以发现,每种移动中,两端点提供的代价只和方向和端点位置有关,与距离无关。对于点x,贡献为$p_x*(-1*a+1*b+k*c)$,abc为三类代价产生次数

显然的,有朴素dp:f(i,s)表示放了前i个位置,放置集合为s。转移为(i,s)=min(f(i-1,s^bit(x)+cost(x,s^bit(x)*i)(bit(x)&s!=0)。时间复杂度$O(m^32^m)$

依靠想象力,我们可以意识到,对于某一点x,其他点之间的位置关系不影响x产生的代价。

我们考虑预处理节点x与所有s产生的贡献,令cost函数变为常数时间。 那么我们有预处理$O(m^22^m)$,dp$O(m^22^m)$.

然后你算一下就发现他卡内存,你根本开不下$m2^m$的数组(dp你可以滚动数组)。

?????

那么我们退而求其次,考虑分组预处理,设每组有k个节点,则有t=m/k(上取整)组。 我们有预处理$O(tm^22^k)$+dp$O(tm^22^m)$,

显然复杂度瓶颈是dp,那么t取2最佳,此时k取12。

这也不行啊这不是连20都跑不过去吗?

努力全部木大 不要停下来啊。

每次转移已经非常优秀($O(m)$),考虑优化dp状态数。

显然大量的状态是冗余的,只有那些i==count(s)的状态才有意义。

那我们可以直接去掉i这一维,因为他其实可以被s表达出来。

那我们有转移方程f(s)=min(f(s^bit(x)+cost(x,s^bit(x)*count(s))(bit(x)&s!=0).

时间复杂度为$O(tm2^m)==O(m2^{m+1})$,预处理count(s)可以卡常,方法同预处理cost。

对于x不属于s,我们考虑跳过x。

预处理2^i对应的i,对于枚举的状态s,直接lowbit后查表得到对应的i;

我们有复杂度$O(tm\sum\limits_{s=1}^{2^m}count(s))$.

即$O(tm2^{m-1})==O(m2^m)$

考场降智想到最后的优化没算清楚就没有写。

放一个$O(m2^m)$代码(其实和$O(m2^{m+1})$就差几行)

#include <iostream>
using namespace std;
const int kmaxs=1<<23;
const int kmaxb=13;
const int kmaxbs=1<<kmaxb;
const int kmaxn=24;
const int kmaxm=100000+5;
const int s2b=12;
const int s1b=0;
const int inf=1e9;
int dp[kmaxs+10];
int t1[kmaxbs][kmaxn];
int t2[kmaxbs][kmaxn];
int a[kmaxm];
int cnt[kmaxn][kmaxn];
int valyx[kmaxn][kmaxn];
int valxy[kmaxn][kmaxn];
int pos[kmaxbs];
char hsh[kmaxs]; 
int n,m;
int K;
int s1,s2;
#define bit(x) (1<<((x)-1))
#define cal_yx(x,y) (valyx[(x)][(y)])
#define cal_xy(x,y) (valxy[(x)][(y)])
/*
int cal_yx(int x,int y)
{
    return cnt[y][x]+cnt[x][y]*K;
}
int cal_xy(int x,int y)
{
    return cnt[x][y]*-1+cnt[y][x]*K;
}*/
int cal(int s,int x,int ts,int bs)
{
    int r=0;
    int y=0;
    for(int i=1;i<=ts;++i)
    {
        y=bs+i;
        if(x==y)continue;
        if(bit(i)&s)//got
        {
            r+=cal_yx(x,y);
        }
        else
        {
            r+=cal_xy(x,y);
        }
    }
    return r;
}
inline int cost2(int x,int s)
{
    int st1=s&((1<<s1)-1);
    s>>=s1;
    int st2=s&((1<<s2)-1);
    return t1[st1][x]+t2[st2][x];
}
inline int my_count(int s)
{
    int st1=s&((1<<s1)-1);
    s>>=s1;
    int st2=s&((1<<s2)-1);
    return pos[st1]+pos[st2];
}
#define lowbit(x) ((x)&(-(x)))
void solve2()
{
    s1=s2b;
    s2=n-s1;
    int c=0;
    for(int s=0;s<(1<<s1);++s)
    {
        c=0;
        for(int k=1;k<=n;++k)
        {
            if(bit(k)&s)
            {
                ++c;
                continue;
            }
            t1[s][k]=cal(s,k,s1,s1b);
        }
        pos[s]=c;
    }
    for(int s=0;s<(1<<s2);++s)
    {
        for(int k=1;k<=n;++k)
        {
            if((k>s2b)&&(bit(k-s2b)&s))
                continue;
            t2[s][k]=cal(s,k,s2,s2b);
        }
    }
    int p=0,i;
    for(int s=1;s<(1<<n);++s)
    {
        dp[s]=inf;
        p=my_count(s);
        for(int j=s;j;j-=lowbit(j))
        {
            i=hsh[lowbit(j)];
            dp[s]=min(dp[s],dp[s^bit(i)]+(p)*cost2(i,s^bit(i)));
        }
    }
}
int cost1(int x,int s)
{
    int r=0;
    for(int y=1;y<=n;++y)
    {
        if(y==x)continue;
        if(s&bit(y))//yx
        {
            r+=cal_yx(x,y);
        }
        else
        {
            r+=cal_xy(x,y);
        }
    }
    return r;
}
void solve1()
{
    int p=0;
    for(int s=1;s<(1<<n);++s)
    {
        dp[s]=inf;
        p=0;
        for(int i=1;i<=n;++i)
        {
            if(s&bit(i))
                ++p;
        }
        for(int i=1;i<=n;++i)
        {
            if(s&bit(i))
            {
                dp[s]=min(dp[s],dp[s^bit(i)]+p*cost1(i,s^bit(i)));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n>>K;
    for(int i=1;i<=m;++i)
    {
        cin>>a[i];
        if(i>1)
            cnt[a[i-1]][a[i]]++;
    }
    for(int x=1;x<=n;++x)
    {
        hsh[bit(x)]=x;
        for(int y=1;y<=n;++y)
        {
            if(x==y)continue;
            valyx[x][y]=cnt[y][x]+cnt[x][y]*K;
            valxy[x][y]=(-cnt[x][y])+cnt[y][x]*K;
        }
    }
    if(n<=12)
    {
        solve1();
    }
    else
    {
        solve2();
    }
    cout<<dp[(1<<n)-1]<<'\n';
    return 0;
}

在luogu上不吸氧也只能跑80,但吸氧之后最慢点0.6s。。。

可能是写丑了常数太大。

//之前睿智了把题解交到d1t1了,靴靴管理员给移动过来。。。。